ac自动机算法正确性还没有理解,算法导论也看不懂。。等懂了回来发算法专题。

 #include <cstdio>
#include <cstring>
using namespace std; const int maxn=1e6+; int n;
char s[maxn]; class AC{
public:
struct node{
node *son[], *fail;
int mark;
}root, *now, *nowson, *p;
AC(){}
void insert(char *s, int len){ //trie,没什么好说的
now=&root;
int v;
for (int i=; i<len; ++i){
v=s[i]-'a';
if (!now->son[v]) now->son[v]=new node();
now=now->son[v];
}
++now->mark;
}
void get_fail(){ //建立失败指针
int head=, tail=;
q[head]=&root;
while (head<tail){ //宽搜
now=q[head];
for (int i=; i<; ++i) //遍历每个儿子
if (now->son[i]){
for (p=now->fail; p&&!p->son[i]; p=p->fail); //通过父亲来找失败指针
//p是0,意味着连root都不行,那只能去root
now->son[i]->fail=(p?p->son[i]:&root);
q[tail++]=now->son[i];
} //else now->son[i]=now->fail->son[i]; //如果没有这个子节点,意味着肯定失配
++head;
}
}
int count(char *s, int len){ //计算有多少个串出现
int ans=;
now=&root;
int v;
for (int i=; i<len; ++i){
//确定适配的树的结点位置
for (v=s[i]-'a'; now&&!now->son[v]; now=now->fail);
now=now?now->son[v]:&root; //如果一直到根还不匹配,那就跳到根
//对于一个匹配串的所有后缀检查
//如果这里ans没设置为-1,那就是求出现次数之和
for (p=now; p&&~p->mark; p=p->fail) {
ans+=p->mark;
p->mark=-;
}
}
return ans;
}
private:
node *q[maxn], head, tail;
}; AC ac; int main(){
scanf("%d", &n);
for (int i=; i<n; ++i){
scanf("%s", s);
int t=strlen(s);
ac.insert(s, t);
}
ac.get_fail();
scanf("%s", s);
printf("%d\n", ac.count(s, strlen(s)));
return ;
}
 #include <cstdio>
#include <cstring>
using namespace std; const int maxn=, maxl1=, maxl2=1e6+; int n, cnt, ans[maxn];
char p[maxn][maxl1];
char t[maxl2]; struct node{
node *son[], *fail;
int id, mark;
}*mem[maxn*maxl1];
class AC{
public:
node *root, *now, *nowson, *p;
AC(){ root=new node(); }
void fresh(){
cnt=;
delete root;
root=new node();
for (int i=; i<memlen; ++i) delete mem[i];
memlen=;
}
void insert(char *s, int len){ //trie,没什么好说的
now=root;
int v;
for (int i=; i<len; ++i){
v=s[i]-'a';
if (!now->son[v]) {
now->son[v]=new node();
mem[memlen++]=now->son[v];//内存回收表
}
now=now->son[v];
}
//如果不去重,这里写成等于1
now->id=cnt++;
++now->mark;
}
void get_fail(){ //建立失败指针
int head=, tail=;
q[head]=root;
while (head<tail){ //宽搜
now=q[head];
for (int i=; i<; ++i) //遍历每个儿子
if (now->son[i]){
for (p=now->fail; p&&!p->son[i]; p=p->fail); //通过父亲来找失败指针
//p是0,意味着连root都不行,那只能去root
now->son[i]->fail=(p?p->son[i]:root);
q[tail++]=now->son[i];
} //else now->son[i]=now->fail->son[i]; //如果没有这个子节点,意味着肯定失配
++head;
}
}
void count(char *s, int len){ //计算有多少个串出现
now=root;
int v;
for (int i=; i<len; ++i){
//确定适配的树的结点位置
for (v=s[i]-'a'; now&&!now->son[v]; now=now->fail);
now=now?now->son[v]:root; //如果一直到根还不匹配,那就跳到根
//对于一个匹配串的所有后缀检查
//如果这里ans没设置为-1,那就是求出现次数之和
for (p=now; p&&~p->mark; p=p->fail) {
ans[p->id]+=p->mark;
//p->mark=-1;
}
}
}
private:
node *q[maxn*maxl1]; //这里忘记加了
int memlen;
}; AC ac; int main(){
scanf("%d", &n);
while (n){
memset(ans, , sizeof(ans));
for (int i=; i<n; ++i){
scanf("%s", p[i]);
int t=strlen(p[i]);
ac.insert(p[i], t);
}
ac.get_fail();
scanf("%s", t);
ac.count(t, strlen(t));
int maxm=;
for (int i=; i<n; ++i)
if (ans[i]>maxm) maxm=ans[i];
printf("%d\n", maxm);
for (int i=; i<n; ++i)
if (ans[i]==maxm) printf("%s\n", p[i]);
scanf("%d", &n);
ac.fresh();
}
return ;
}
05-02 16:12
查看更多