HDU 2222(ACオートマトンの2種類のテンプレート)
4172 ワード
タイトルリンク
問題はn個の単語をあげて、それからテキスト列をあげます.このテキスト列に現れるn個の単語の数を尋ねる.
iノードの最後の単語数を1つのval[i]で保存すればよい.
2つのテンプレート:
最初のブログ:ブログ
#include
using namespace std;
const int M=60,N=1e6+10;
char s[N];
struct ac_auto
{
int ne[N][26],val[N],fail[N],sz;
void init()
{
memset(ne[0],0,sizeof(ne[0]));
sz=0;
}
void insert(char *s)//
{
int o=0;
for(int i=0;s[i];++i)
{
int c=s[i]-'a';
if(ne[o][c]==0){
ne[o][c]=++sz;
val[sz]=0;
memset(ne[sz],0,sizeof(ne[sz]));
}
o=ne[o][c];
}
val[o]++;
}
void build()//bfs fail ,
{
queueque;
for(int i=0;i<26;++i)
if(ne[0][i]){
que.push(ne[0][i]);
fail[ne[0][i]]=0;// fail
}
while(que.size())
{
int o=que.front();que.pop();
for(int i=0;i<26;++i){
if(ne[o][i])
{
int v=ne[o][i];
int fa=fail[o];
while(fa&&!ne[fa][i]) fa=fail[fa];// i , fail , i
fail[v]=ne[fa][i];
que.push(v);
}
}
}
}
int query(char *s)// fail
{
int o=0,ans=0;
for(int i=0;s[i];++i)
{
int c=s[i]-'a';
while(!ne[o][c]&&o) o=fail[o];
o=ne[o][c];
int tmp=o;
while(tmp)
{
ans+=val[tmp];
val[tmp]=0;
tmp=fail[tmp];
}
}
return ans;
}
}ac;
int main()
{
int _;cin>>_;while(_--)
{
int n;
scanf("%d",&n);
ac.init();
for(int i=1;i<=n;++i){
scanf("%s",s);
ac.insert(s);
}
ac.build();
scanf("%s",s);
printf("%d
",ac.query(s));
}
}
2つ目のテンプレート:
#include
using namespace std;
const int N=1e6+10;
int n, m;
char s[N];
struct node
{
int tr[N][26], fail[N], num[N], cnt = 0;
void init(){
memset(tr[0], 0, sizeof(tr[0])), cnt=0;
}
void insert(char s[]){
int n = strlen(s + 1), root = 0;
for(int i = 1; i <= n; ++i){
if(!tr[root][s[i] - 'a']) {
tr[root][s[i] - 'a'] = ++cnt;
memset(tr[cnt], 0, sizeof(tr[cnt])), num[cnt] = 0;
}
root = tr[root][s[i]-'a'];
}
//printf("cnt:%d root:%d
", cnt, root);
num[root]++;
}
void getfail(){
queue que;
for(int i = 0; i < 26; ++i){
if(tr[0][i]) que.push(tr[0][i]), fail[tr[0][i]] = 0;
}
while(que.size()){
int now = que.front(); que.pop();
for(int i = 0; i < 26; ++i){
if(tr[now][i]) fail[tr[now][i]] = tr[fail[now]][i], que.push(tr[now][i]);
else tr[now][i] = tr[fail[now]][i];
}
}
}
int find(char s[]){
int ans = 0;
int root = 0, len = strlen(s+1);
for(int i = 1; i <= len; ++i){
root = tr[root][s[i] - 'a'];
int tmp = root;
while(tmp){
//printf("tmp:%d
",tmp);
ans += num[tmp];
num[tmp] = 0;
tmp = fail[tmp];
}
}
return ans;
}
}ac;
int main()
{
int _;scanf("%d", &_);while(_--){
ac.init();
scanf("%d", &n);
for(int i = 1; i <= n; ++i){
scanf("%s", s + 1);
ac.insert(s);
}
ac.getfail();
scanf("%s", s+1);
printf("%d
", ac.find(s));
}
return 0;
}
2つのテンプレートの違いはfailポインタを構築するときに異なることです
2つ目は1つ目より少し速いです(個人的には理解しています).failポインタを構築するときにfailを繰り返し踊らないからです.