ZOJ 3228 Searching the String(AC自动机)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3228
题意:
给你N个模板串和一个文本串，问你这些模板串在文本串中最多出现了多少次。注意：模板串可能重复，且模板串有两种类型，第一种是：对于同一个模板，其前后匹配的位置可以重叠(即两个同样的单词前后重叠了)。第二种模板不能重叠。
分析:
首先该题的模板可以重复,不论是type1还是type0的,但是我们程序中对于每个模板不区分类型,我们直接插入到AC自动机去,但是每个单词节点有两个cnt值,cnt[0]表示该单词节点可重叠时的计数个数.cnt[1]表示该单词节点不可重叠时的计数个数.并且用time属性记录该单词节点(不可重叠那个属性)上次匹配文本串时,出现的位置.然后如果下次又匹配了文本串,就要用当前位置和time属性比较,看看两者之差是不是>=单词的长度(所以还需要一个单词节点长度属性len).这里做了贪心选择，优先选择先出现的同一个模板。
由于模板可以重复,我们这里要处理重复模板,但是我们不用map去映射,我们对于每个模板查询一次AC自动机即可.然后按照模板的类型返回它的值即可.应该比用map要快.而且简单。
具体细节还是需要看代码体会.
AC代码: 模板各种写错,不过过样例后直接AC了.
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxnode = 101000*5;
const int sigma_size=26;
struct AC_Automata
{
int ch[maxnode][sigma_size];
int val[maxnode];//表示是否是单词节点
int time[maxnode],len[maxnode];//单词节点的长度,以及上次type1的单词出现在文本串的位置+1处
int last[maxnode],f[maxnode];
int cnt[maxnode][2];//计数
int sz;
void init()
{
sz=1;
memset(ch[0],0,sizeof(ch[0]));
val[0]=last[0]=f[0]=0;
}
void insert(char *s)//不分类型的插入单词
{
int n=strlen(s),u=0;
for(int i=0;i<n;i++)
{
int id=s[i]-'a';
if(ch[u][id]==0)
{
ch[u][id]=sz;
memset(ch[sz],0,sizeof(ch[sz]));
val[sz++]=0;
}
u=ch[u][id];
}
val[u]=1;
time[u]=0;
len[u]=n;
cnt[u][0]=cnt[u][1]=0;
}
void print(int i,int pos)
{
if(val[i])
{
cnt[i][0]++;
if(time[i]+len[i]<=pos)//判断是否有重叠
{
time[i]=pos;
cnt[i][1]++;
}
print(last[i],pos);
}
}
void find(char *s)
{
int n=strlen(s),j=0;
for(int i=0;i<n;i++)
{
int id=s[i]-'a';
while(j && ch[j][id]==0) j=f[j];
j=ch[j][id];
if(val[j]) print(j,i+1);
else if(last[j]) print(last[j],i+1);
}
}
int find_T(char *s,int type)
{
int n=strlen(s),u=0;
for(int i=0;i<n;i++)
{
int id=s[i]-'a';
u=ch[u][id];
}
return cnt[u][type];
}
void getFail()
{
queue<int> q;
for(int i=0;i<sigma_size;i++)
{
int u=ch[0][i];
if(u)
{
last[u]=f[u]=0;
q.push(u);
}
}
while(!q.empty())
{
int r=q.front();q.pop();
for(int i=0;i<sigma_size;i++)
{
int u=ch[r][i];
if(!u)continue;
q.push(u);
int v=f[r];
while(v && ch[v][i]==0) v=f[v];
f[u]=ch[v][i];
last[u] = (val[f[u]])?f[u]:last[f[u]];
}
}
}
};
AC_Automata ac;
const int MAXN=100000+1000;
char str[MAXN];
char t[MAXN][7];
int type[MAXN];
int main()
{
int kase=0;
while(scanf("%s",str)==1)
{
ac.init();
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d%s",&type[i],t[i]);
ac.insert(t[i]);
}
ac.getFail();
ac.find(str);
printf("Case %d\n",++kase);
for(int i=0;i<n;i++)
{
printf("%d\n",ac.find_T(t[i],type[i]));
}
printf("\n");
}
return 0;
}