結果

問題 No.430 文字列検索
ユーザー kopricky
提出日時 2017-11-17 18:16:07
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 12 ms / 2,000 ms
コード長 2,315 bytes
コンパイル時間 1,864 ms
コンパイル使用メモリ 177,012 KB
実行使用メモリ 6,884 KB
最終ジャッジ日時 2024-11-10 00:18:23
合計ジャッジ時間 2,155 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define each(a,b) for(auto (a): (b))
#define all(v) (v).begin(),(v).end()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl
#define sset(s) cout<<#s<<":";each(kbrni,s)cout<<" "<<kbrni;cout<<endl
#define smap(m) cout<<#m<<":";each(kbrni,m)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int>P;

const int MAX_N = 100005;
const int NUMC = 26;

class Trie {
public:
	vector<vector<int> > V;
	int find(string s) {
		int cur=0;
		rep(i,s.size()){
            if((cur=V[cur][s[i]+1])==0) return -1;
        }
		return cur;
	}
	void create(vector<string> S) { // 0 is rep backtrack
		V.clear();
		V.push_back(vector<int>(NUMC+1));
		sort(S.begin(),S.end());
		rep(i,S.size()){
			int cur=0;
			rep(j,S[i].size()){
				if(V[cur][S[i][j]+1]==0) V.push_back(vector<int>(NUMC+1)),V[cur][S[i][j]+1]=V.size()-1;
				cur=V[cur][S[i][j]+1];
			}
		}
	}
};

class ACmatch_num {
public:
	Trie t;
	vector<int> acc;
	int ma;
	void create(vector<string> S) {
		int i;
		ma=S.size();
		t.create(S);
		acc.clear();
		acc.resize(t.V.size());
		rep(i,S.size()) acc[t.find(S[i])]++;
		queue<int> Q;
		rep(i,NUMC) if(t.V[0][i+1]) t.V[t.V[0][i+1]][0]=0, Q.push(t.V[0][i+1]);

		while(!Q.empty()) {
			int k=Q.front(); Q.pop();
			rep(i,NUMC) if(t.V[k][i+1]) {
				Q.push(t.V[k][i+1]);
				int pre=t.V[k][0];
				while(pre && t.V[pre][i+1]==0) pre=t.V[pre][0];
				t.V[t.V[k][i+1]][0]=t.V[pre][i+1];
				acc[t.V[k][i+1]] += acc[t.V[pre][i+1]];
			}
		}
	}
	int match(string S) {
		int R=0;
		int cur=0;
		rep(i,S.size()){
			while(cur && t.V[cur][S[i]+1]==0) cur=t.V[cur][0];
			cur=t.V[cur][S[i]+1];
			R += acc[cur];
		}
		return R;
	}
};

int main()
{
    string s;
	cin >> s;
	rep(i,s.size()){
		s[i] -= 'A';
	}
	int m;
	cin >> m;
	vector<string> t(m);
	rep(i,m){
		cin >> t[i];
		rep(j,t[i].size()){
			t[i][j] -= 'A';
		}
	}
	ACmatch_num ac;
	ac.create(t);
	cout << ac.match(s) << "\n";
}
0