BY 九野
做了一道题，用我的那种写法华丽丽的超时了。，无奈学一学数组实现的
#include<stdio.h>
#include<string.h>
#include<queue>
#include<iostream>
using namespace std;
const int maxnode=250*1000+10000;//maxnode=单词数*单词长度+常数
const int sg_size=26;
struct Trie
{
int ch[maxnode][sg_size];
int val[maxnode];//该单词在模式串出现的次数
int last[maxnode];
int f[maxnode];//失配函数
int num[maxnode];//该单词在文本串中出现的次数
int pre[maxnode];//该单词的前驱
int len[maxnode];//以该单词结尾的单词长度
int Char[maxnode];//该单词相应的字母
int road[maxnode];//路径压缩优化，针对模式串出现的种类
int sz;
int newnode()
{
val[sz]=f[sz]=last[sz]=len[sz]=num[sz]=0;
memset(ch[sz],0,sizeof(ch[sz]));
return sz++;
}
void init()
{
sz=0;
newnode();
}
int idx(char c)
{
return c-'A';
}
int insert(char *s)
{
int u=0,i;
for(i=0;s[i];i++)
{
int c=idx(s[i]);
if(!ch[u][c])
ch[u][c]=newnode();
pre[ch[u][c]]=u;
Char[ch[u][c]]=s[i];
len[ch[u][c]]=len[u]+1;
road[ch[u][c]]=1;
u=ch[u][c];
}
val[u]=1;
num[u]=0;
return u;
}
void getfail()
{
queue<int>q;
int i;
for(i=0;i<sg_size;i++)
{
if(ch[0][i])
q.push(ch[0][i]);
}
int r,c,u,v;
while(!q.empty())
{
r=q.front();
q.pop();
for(c=0;c<sg_size;c++)
{
u=ch[r][c];
if(u)
continue;
q.push(u);
v=f[r];
while(v&&ch[v][c]==0)
v=f[v];//沿失配边走上去 假设失配后有节点 且 其子节点c存在则结束循环
f[u]=ch[v][c];
}
}
}
void find(char *s)
{ //计算模式串出现的个数：（每种多次出现算多次）
int j=0;
for(int i=0;s[i];i++)
{
int c=idx(s[i]);
while(j&&ch[j][c]==0)
j=f[j];
j=ch[j][c];
int temp=j;
while(temp)
{
num[temp]++;
temp=f[temp];
}
}
}
void find_kind(char *s,int &ans)
{
//计算种数， 反复出现的不再计算(若多个询问则要在此处加for(i=0->sz)lu[i]=1;
int j=0,i,c,temp;
for(i=0;s[i];i++)
{
c=idx(s[i]);
while(j&&ch[j][c]==0)
j=f[j];
j=ch[j][c];
temp=j;
while(temp&&road[temp])
{
if(val[temp])
{
++ans;
val[temp]=0;
}
road[temp]=0;
temp=f[temp];
}
}
}
}ac;
int main()
{
}