結果

問題 No.430 文字列検索
ユーザー ixmelixmel
提出日時 2017-11-27 14:53:22
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 18 ms / 2,000 ms
コード長 4,165 bytes
コンパイル時間 952 ms
コンパイル使用メモリ 99,852 KB
実行使用メモリ 8,664 KB
最終ジャッジ日時 2023-08-18 07:21:44
合計ジャッジ時間 1,986 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
//#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
//#define mt make_tuple
//typedef tuple<pii,int,int> tp;
//typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-7;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
#define MAX 26
#define OFFSET 'A'
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() {}
	
	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()) {
//			rep(i,correct.size())cout<<" "<<correct[i];cout<<endl;
			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]);
			}
		}
//			rep(i,correct.size())cout<<" "<<correct[i];cout<<endl;
	}
	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 n;
	cin>>n;
	vs p(n);
	rep(i,n)cin>>p[i];
	Aho_Corasick ac;
	rep(i,n)ac.add(p[i]);
	ac.build();
	vi out;
	cout<<ac.match(s,out)<<endl;
}
0