/*
啥也不说了，直接套模板。。。
*/
1 #include<iostream> 2 #include<map> 3 #include<string> 4 #include<cstring> 5 #include<queue> 6 #define N 500000 7 using namespace std; 8 9 class AC_Atomata 10 { 11 public: 12 int nodeN;//trie树的节点个数 13 int trie[N][26];//trie树 14 int f[N];//失配函数 15 //map<string, int>ms;//字符串到字符串编号的映射，防止出现多个字符串的模板 16 int last[N];// last[j]表示节点j沿着失配指针往回走时遇到的下一个单词节点的编号 17 int cnt;//最多在主串中出现的单词数 18 int val[N];//标记该节点是否为字符串的端点，该题中val[j]表示以节点j所对应的字符所结束的相同字符串的个数 19 int vis[N];//标记该节点已经访问过了 20 queue<int>q; 21 void init(); 22 void buildTrie(char *p); 23 void getFail(); 24 void find(char *T); 25 void countWords(int k); 26 }; 27 28 void AC_Atomata::init() 29 { 30 nodeN=0; 31 ms.clear(); 32 memset(vis, 0, sizeof(vis)); 33 memset(trie[0], 0, sizeof(trie[0])); 34 //memset(cnt, 0, sizeof(cnt)); 35 cnt=0; 36 } 37 38 void AC_Atomata::buildTrie(char *p) 39 { 40 int i, u=0; 41 for(i=0; p[i]; ++i) 42 { 43 int k=p[i]-'a'; 44 if(!trie[u][k]) 45 { 46 memset(trie[nodeN+1], 0, sizeof(trie[nodeN+1])) ; 47 trie[u][k]=++nodeN; 48 val[nodeN]=0; 49 } 50 u=trie[u][k]; 51 } 52 ++val[u]; 53 //ms[string(p)]=v; 54 } 55 56 void AC_Atomata::getFail() 57 { 58 int u, v, r, c; 59 while(!q.empty()) q.pop(); 60 f[0]=0; 61 for(c=0; c<26; ++c) 62 { 63 u=trie[0][c]; 64 if(u) 65 { 66 f[u]=0; 67 q.push(u); 68 last[u]=0; 69 } 70 } 71 while(!q.empty()) 72 { 73 r=q.front(); 74 q.pop(); 75 for(c=0; c<26; ++c) 76 { 77 u=trie[r][c]; 78 if(!u) continue; 79 q.push(u); 80 v=f[r]; 81 while(v && !trie[v][c]) v=f[v]; 82 f[u]=trie[v][c]; 83 last[u]=val[f[u]] ? f[u] : last[f[u]]; 84 } 85 } 86 } 87 88 void AC_Atomata::countWords(int k) 89 { 90 if(k && !vis[k]) 91 { 92 //++cnt[val[k]];//k就是该单词所对应的最后一个字符的节点编号，val[k]是这个单词再输入时候的编号 93 vis[k]=1;//表示以该节点结束的字符串已经访问过了，如果主串中再出现该字符串则不会再计算在内 94 cnt+=val[k];// 95 countWords(last[k]); 96 } 97 } 98 99 void AC_Atomata::find(char *T) 100 { 101 int i, j; 102 for(i=0, j=0; T[i]; ++i) 103 { 104 int c=T[i]-'a'; 105 while(j && !trie[j][c]) j=f[j];//一直找到可以匹配的字符节点 106 j=trie[j][c]; 107 if(val[j])//单词的最后一个字符 108 countWords(j); 109 else if(last[j])//如果不是某个单词的最后一个节点 110 countWords(last[j]); 111 } 112 } 113 114 AC_Atomata ac; 115 116 char T[1000005]; 117 char s[55]; 118 119 int main() 120 { 121 int t, n, i; 122 scanf("%d", &t); 123 while(t--) 124 { 125 ac.init(); 126 scanf("%d", &n); 127 for(i=1; i<=n; ++i) 128 { 129 scanf("%s", s); 130 ac.buildTrie(s); 131 } 132 scanf("%s", T); 133 ac.getFail(); 134 ac.find(T); 135 printf("%d\n", ac.cnt); 136 } 137 return 0; 138 }
/*
咱再换一种方式来写，赶脚这种方式更靠谱一些！
*/
1 #include<queue> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdio> 5 #include<string> 6 #define N 500000 7 using namespace std; 8 9 class TRIE 10 { 11 public: 12 int ch[26];//建立trie树的孩子节点个数 13 int val;//标记该节点是否是单词的结束节点 14 int fail;//该节点失配时要移向的节点的编号 15 int last;//后缀连接，示节该点沿着失配指针往回走时遇到的下一个单词节点的编号 16 int vis;//标记以该点字符所结束的字符串是否已经访问过了 17 }; 18 19 class AC_Atomata 20 { 21 public: 22 TRIE trie[N];//建立节点 23 int nodeN;//trie树的节点的个数 24 int cnt;//记录节点单词在主串出现的次数 25 AC_Atomata() 26 { 27 nodeN=0; 28 cnt=0; 29 trie[0].val=trie[0].vis=0; 30 memset(trie[0].ch, 0, sizeof(trie[0].ch)); 31 while(!q.empty()) q.pop(); 32 } 33 queue<int>q; 34 void buildTrie(char *p); 35 void getFail(); 36 void find(char *T); 37 void countWords(int k); 38 }; 39 40 void AC_Atomata::buildTrie(char *p) 41 { 42 int i, u; 43 for(i=0, u=0; p[i]; ++i) 44 { 45 int k=p[i]-'a'; 46 if(!trie[u].ch[k]) 47 { 48 trie[u].ch[k]=++nodeN; 49 memset(trie[nodeN].ch, 0, sizeof(trie[nodeN].ch)); 50 trie[nodeN].val=trie[nodeN].vis=0; 51 } 52 u=trie[u].ch[k]; 53 } 54 ++trie[u].val; 55 } 56 57 void AC_Atomata::getFail() 58 { 59 int r, u, v, c; 60 trie[0].fail=0; 61 for(c=0; c<26; ++c) 62 { 63 u=trie[0].ch[c]; 64 if(u) 65 { 66 q.push(u); 67 trie[u].fail=0; 68 trie[u].last=0; 69 } 70 } 71 while(!q.empty()) 72 { 73 r=q.front(); 74 q.pop(); 75 for(c=0; c<26; ++c) 76 { 77 u=trie[r].ch[c]; 78 if(!u) continue; 79 q.push(u); 80 v=trie[r].fail; 81 while(v && !trie[v].ch[c]) v=trie[v].fail; 82 v=trie[v].ch[c];//v 节点就是在沿着失配指针往回走时遇到的下一个单词某个字符节点的编号 83 trie[u].fail=v; 84 trie[u].last=trie[v].val ? v : trie[v].last;//last记录的总是一个完整的单词最后一个字符节点的编号 85 } 86 } 87 } 88 89 void AC_Atomata:: find(char *T) 90 { 91 int i, j; 92 for(i=0, j=0; T[i]; ++i) 93 { 94 int k=T[i]-'a'; 95 while(j && !trie[j].ch[k]) j=trie[j].fail; 96 j=trie[j].ch[k]; 97 if(trie[j].val) 98 countWords(j); 99 else if(trie[j].last) 100 countWords(trie[j].last); 101 } 102 } 103 104 void AC_Atomata::countWords(int n) 105 { 106 if(n && !trie[n].vis) 107 { 108 trie[n].vis=1; 109 cnt+=trie[n].val; 110 countWords(trie[n].last); 111 } 112 } 113 114 AC_Atomata ac; 115 char T[100000]; 116 char s[55]; 117 118 int main() 119 { 120 int t, n; 121 scanf("%d", &t); 122 while(t--) 123 { 124 scanf("%d", &n); 125 for(int i=1; i<=n; ++i) 126 { 127 scanf("%s", s); 128 ac.buildTrie(s); 129 } 130 scanf("%s", T); 131 ac.getFail(); 132 ac.find(T); 133 printf("%d\n", ac.cnt); 134 } 135 return 0; 136 }
