結果

問題 No.430 文字列検索
ユーザー wk1080idwk1080id
提出日時 2017-11-27 19:49:37
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 15 ms / 2,000 ms
コード長 3,377 bytes
コンパイル時間 1,098 ms
コンパイル使用メモリ 98,876 KB
実行使用メモリ 8,124 KB
最終ジャッジ日時 2023-08-18 07:38:53
合計ジャッジ時間 2,131 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 15 ms
8,124 KB
testcase_02 AC 7 ms
4,696 KB
testcase_03 AC 7 ms
4,604 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 3 ms
4,380 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 12 ms
5,756 KB
testcase_12 AC 12 ms
5,680 KB
testcase_13 AC 12 ms
5,740 KB
testcase_14 AC 11 ms
5,652 KB
testcase_15 AC 9 ms
5,668 KB
testcase_16 AC 9 ms
5,700 KB
testcase_17 AC 9 ms
5,720 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<n;i++)
#define loop(i,a,n) for(i=a;i<n;i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef pair<int,int> pii;

#define MAX 26
#define OFFSET 'A' //atention!!

struct Node{
  int nxt[MAX+1]; // 次のalphabeteのノード番号
  int exist; // 子ども以下に存在する文字列の数の合計
  vi accept; // その文字列id
  Node() : exist(0){memset(nxt, -1, sizeof(nxt));}
};

struct Trie{
  vector<Node>nodes;
  int root;
  Trie() : root(0){nodes.push_back(Node());}

  void update_direct(int node,int id){
    nodes[node].accept.push_back(id);
  }
  void update_child(int node,int child,int id){
    ++nodes[node].exist;
  }
  void add(const string &str,int str_index,int node_index,int id){
    if(str_index == str.size()) 
      update_direct(node_index, id);
    else{
      const int c = str[str_index] - OFFSET;
      if(nodes[node_index].nxt[c] == -1) {
	nodes[node_index].nxt[c] = (int) nodes.size();
	nodes.push_back(Node());
      }
      add(str, str_index + 1, nodes[node_index].nxt[c], id);
      update_child(node_index, nodes[node_index].nxt[c], id);
    }
  }
  void add(const string &str,int id){add(str, 0, 0, id);}
  void add(const string &str){add(str, nodes[0].exist);}
  int size(){return (nodes[0].exist);}
  int nodesize(){return ((int) nodes.size());}
};

struct Aho_Corasick : Trie{
  static const int FAIL = MAX;
  vi correct;
  Aho_Corasick() : Trie() {}

  int i;  

  void build(){
    correct.resize(nodes.size());
    rep(i,nodes.size())correct[i]=(int)nodes[i].accept.size();

    queue<int> que;
    rep(i,MAX+1){
      if(~nodes[0].nxt[i]) {
	nodes[nodes[0].nxt[i]].nxt[FAIL] = 0;
	que.emplace(nodes[0].nxt[i]);
      }else nodes[0].nxt[i] = 0;
    }
    while(!que.empty()) {
      Node now = nodes[que.front()];
      correct[que.front()] += correct[now.nxt[FAIL]];
      que.pop();
      rep(i,MAX){
	if(now.nxt[i] == -1) continue;
	int fail = now.nxt[FAIL];
	while(nodes[fail].nxt[i] == -1) {
	  fail = nodes[fail].nxt[FAIL];
	}
	nodes[now.nxt[i]].nxt[FAIL] = nodes[fail].nxt[i];

	auto &u = nodes[now.nxt[i]].accept;
	auto &v = nodes[nodes[fail].nxt[i]].accept;
	vi accept;
	set_union(all(u),all(v),back_inserter(accept));
	u=accept;
	que.emplace(now.nxt[i]);
      }
    }
  }
  int match(const string &str,vi &result,int now=0){
    result.assign(size(),0);
    int count=0;
    for(auto &c:str) {
      while(nodes[now].nxt[c-OFFSET]==-1)now=nodes[now].nxt[FAIL];
      now = nodes[now].nxt[c-OFFSET];
      count += correct[now];
      for(auto &v:nodes[now].accept)result[v]++;
    }
    return count;
  }
  int next(int now,char c){
    while(nodes[now].nxt[c-OFFSET]==-1)now=nodes[now].nxt[FAIL];
    return nodes[now].nxt[c-OFFSET];
  }
};

int main(){
  string s;
  cin>>s;
  int i,n;
  cin>>n;
  vector<string> c(n);
  rep(i,n)cin>>c[i];
  Aho_Corasick ac;
  rep(i,n)ac.add(c[i]);
  ac.build();
  vi tmp;
  cout<<ac.match(s,tmp)<<endl;
}
0