屌丝的字典树。。。醉了。。。
#include#include #include #include #include #include #include using namespace std;struct Trie{ int next[500010][26],fail[500010],isend[500010]; int root,L; int newnode() { for(int i = 0;i < 26;i++)//这个串的跳转清空 next[L][i] = -1;//清空要根据情况而定,常用0为转移提供方便 isend[L++] = 0;//不是节点层 return L-1;//返回这个点的序号 } void init() { L = 0; root = newnode();//给根一个点 } void Insert(char buf[]) { int len = strlen(buf); int now = root; for(int i = 0;i < len;i++) { if(next[now][buf[i]-'a'] == -1)//当前字典层中没有这个字符 next[now][buf[i]-'a'] = newnode();//指向生成新的点，并且这点有字符 now = next[now][buf[i]-'a'];//去新的点位继续操作 } isend[now]++;//这层是结点层，标记 } void build() { queue Q; fail[root] = root;//根节点仍然是根节点 for(int i = 0;i < 26;i++)//对第一个字符遍历 if(next[root][i] == -1)//没有此字符开头 next[root][i] = root;//跳转到根 else//有此字符开头的 { fail[next[root][i]] = root;//这个行位的失败指针为根 Q.push(next[root][i]);//行放入队列 } while( !Q.empty() )//还有字符 { int now = Q.front();//逐层拿出第一个 Q.pop(); for(int i = 0;i < 26;i++)//对这一行 if(next[now][i] == -1)//如果下一行没有这个字符 next[now][i] = next[fail[now]][i];//他的下一个的这个位置，是回到这个点父节点的下一个（回头） else//如果有这个字符 { //int cur=fail[now];//子节点是终点，他也是终点 //while(cur&&next[cur][i]==0) // cur=fail[cur]; //fail[next[now][i]]=next[cur][i]; //if (isend[fail[next[now][i]]]) isend[next[now][i]]=1; fail[next[now][i]]=next[fail[now]][i];//他的下一个的这个位置的失败指针，是这个点父节点的下一个 Q.push(next[now][i]);//下一行继续 } } } int query(char buf[]) { int len = strlen(buf); int now = root; int res = 0; for(int i = 0;i < len;i++) { now = next[now][buf[i]-'a']; int temp = now; while( temp != root ) { res += isend[temp]; isend[temp] = 0; temp = fail[temp]; } } return res; } void debug() { for(int i = 0;i < L;i++) { printf("id = %3d,fail = %3d,end = %3d,chi = [",i,fail[i],isend[i]); for(int j = 0;j < 26;j++) printf("%2d",next[i][j]); printf("]\n"); } }};char buf[1000010];Trie ac;int main(){ int T; int n; scanf("%d",&T); while( T-- ) { scanf("%d",&n); ac.init(); for(int i = 0;i < n;i++) { scanf("%s",buf); ac.Insert(buf); } ac.build(); scanf("%s",buf); printf("%d\n",ac.query(buf)); } return 0;}