結果

問題 No.430 文字列検索
ユーザー noynotenoynote
提出日時 2017-11-27 19:19:26
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 15 ms / 2,000 ms
コード長 3,109 bytes
コンパイル時間 1,469 ms
コンパイル使用メモリ 174,696 KB
実行使用メモリ 7,784 KB
最終ジャッジ日時 2024-11-10 00:18:31
合計ジャッジ時間 2,050 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 15 ms
7,784 KB
testcase_02 AC 6 ms
5,248 KB
testcase_03 AC 5 ms
5,248 KB
testcase_04 AC 1 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 1 ms
5,248 KB
testcase_07 AC 1 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 1 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 10 ms
5,576 KB
testcase_12 AC 10 ms
5,736 KB
testcase_13 AC 10 ms
5,732 KB
testcase_14 AC 9 ms
5,576 KB
testcase_15 AC 8 ms
5,576 KB
testcase_16 AC 7 ms
5,576 KB
testcase_17 AC 8 ms
5,596 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
//const int INF = 1e8;
using namespace std;


const int MAX = 26;
const char OFFSET = 'A';

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

class Trie{
	private:
		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);
			}
		}

	public:
		vector<Node>nodes;
		int root;
		Trie() : root(0){nodes.push_back(Node());}
		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());}
};

class AhoCorasick : public Trie{
	public: 
		static const int FAIL = MAX;
		vector<int> correct;
		AhoCorasick() : 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()) {
				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;
					vector<int> accept;
					set_union(all(u),all(v),back_inserter(accept));
					u=accept;
					que.emplace(now.nxt[i]);
				}
			}
		}
		int match(const string &str,vector<int> &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 t;
	int n;
	cin >> t >> n;

	AhoCorasick aho;
	rep(i,n){
		string s;
		cin >> s;

		aho.add(s);
	}
	aho.build();

	vector<int> result;
	cout << aho.match(t, result) << endl;
}
0