結果

問題 No.430 文字列検索
ユーザー ateate
提出日時 2020-08-11 13:16:30
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 74 ms / 2,000 ms
コード長 2,120 bytes
コンパイル時間 3,022 ms
コンパイル使用メモリ 240,848 KB
実行使用メモリ 6,904 KB
最終ジャッジ日時 2024-11-10 00:45:34
合計ジャッジ時間 3,794 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 65 ms
6,904 KB
testcase_02 AC 65 ms
6,816 KB
testcase_03 AC 61 ms
6,816 KB
testcase_04 AC 1 ms
6,816 KB
testcase_05 AC 1 ms
6,820 KB
testcase_06 AC 1 ms
6,820 KB
testcase_07 AC 2 ms
6,816 KB
testcase_08 AC 48 ms
6,820 KB
testcase_09 AC 2 ms
6,820 KB
testcase_10 AC 3 ms
6,824 KB
testcase_11 AC 74 ms
6,816 KB
testcase_12 AC 69 ms
6,816 KB
testcase_13 AC 71 ms
6,816 KB
testcase_14 AC 66 ms
6,816 KB
testcase_15 AC 53 ms
6,816 KB
testcase_16 AC 57 ms
6,816 KB
testcase_17 AC 57 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>

using std::cout;
using std::endl;

struct trie{
  struct node{
    std::vector<int> next_alp;
    int val;
    node():next_alp(26,-1),val(-1){}
    node(int k):next_alp(26,-1),val(k){}
    node(int c,int id):next_alp(26,-1),val(-1){
      next_alp[c] = id;
    }
  };
  std::vector<node> nodes;
  int k;
  trie():nodes(26),k(0){}
  void dump(){
    for(int i=0;i<nodes.size();++i){
      auto& n = nodes[i];
      if(std::all_of(n.next_alp.begin(),n.next_alp.end(),[](int v){return v==-1;}))continue;
      cout<<i<<":"<<endl;
      for(auto x:n.next_alp)cout<<x<<" ";
      cout<<endl;
      cout<<n.val<<endl;
    }
    cout<<endl;
  }
  std::vector<int> encode(std::string const& s){
    int n = s.size();
    std::vector<int> a(n);
    for(int i=0;i<n;++i)a[i]=s[i]-'a';
    return a;
  }
  void add_impl(std::vector<int> const& a,int ai,int nodei){
    if(ai+1==a.size()){
      nodes[nodei].val = k++;
      return;
    }
    auto& nxt = nodes[nodei].next_alp[a[ai+1]];
    if(nxt==-1){
      nxt = nodes.size();
      nodes.emplace_back();
    }
    add_impl(a,ai+1,nxt);
  }
  void add(std::string const& s){
    add_impl(encode(s),0,s[0]-'a');
  }
  bool find(std::string const& s){
    auto cur = nodes[s[0]-'a'];
    for(int i=0;i+1<s.size();++i){
      int c = s[i+1]-'a';
      if(cur.next_alp[c]==-1)return false;
      cur = nodes[cur.next_alp[c]];
    }
    return true;
  }
  int get(std::string const& s){
    int res = 0;
    auto cur = nodes[s[0]-'a'];
    if(cur.val!=-1){
      res++;
    }
    for(int i=0;i+1<s.size();++i){
      int c = s[i+1]-'a';
      if(cur.next_alp[c]==-1)break;
      cur = nodes[cur.next_alp[c]];
      if(cur.val!=-1){
        res++;
      }
    }
    return res;
  }
};

signed main(){

  using namespace std;

  string s;
  cin>>s;
  int m;
  cin>>m;
  trie t;
  for(int i=0;i<m;++i){
    string c;
    cin>>c;
    for(auto& ci:c)ci=tolower(ci);
    t.add(c);
  }
  for(auto& si:s)si=tolower(si);
  int ans = 0;
  for(int i=0;i<s.size();++i){
    int tmp = t.get(s.substr(i));
    ans += tmp;
  }
  cout<< ans <<endl;

}
0