結果

問題 No.430 文字列検索
ユーザー kmjp
提出日時 2016-10-02 22:41:36
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 10 ms / 2,000 ms
コード長 2,136 bytes
コンパイル時間 1,955 ms
コンパイル使用メモリ 178,820 KB
実行使用メモリ 6,788 KB
最終ジャッジ日時 2024-11-10 00:01:45
合計ジャッジ時間 2,226 ms
ジャッジサーバーID
(参考情報)
judge1 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;
#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------
const int NUMC=26;
class Trie {
public:
vector<vector<int> > V;
int find(string s) {
int cur=0;
ITR(it,s) if((cur=V[cur][*it+1])==0) return -1;
return cur;
}
void create(vector<string> S) { // 0 is for backtrack
V.clear();
V.push_back(vector<int>(NUMC+1));
sort(S.begin(),S.end());
ITR(it,S) {
int cur=0;
ITR(c,(*it)) {
if(V[cur][*c+1]==0) V.push_back(vector<int>(NUMC+1)),V[cur][*c+1]=V.size()-1;
cur=V[cur][*c+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());
FOR(i,S.size()) acc[t.find(S[i])]++;
queue<int> Q;
FOR(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();
FOR(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;
ITR(it,S) {
while(cur && t.V[cur][*it+1]==0) cur=t.V[cur][0];
cur=t.V[cur][*it+1];
R += acc[cur];
}
return R;
}
};
string S;
int M;
vector<string> C;
void solve() {
int i,j,k,l,r,x,y; string s;
cin>>S>>M;
FORR(c,S) c-='A';
FOR(i,M) {
cin>>s;
FORR(c,s) c-='A';
C.push_back(s);
}
ACmatch_num ac;
ac.create(C);
cout << ac.match(S) <<endl;
}
int main(int argc,char** argv){
string s;int i;
if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
FOR(i,argc-1) s+=argv[i+1],s+='\n';
FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
solve(); return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0