/*
一道AC自動機模板題，超時次數20+，改了半天終於AC了，代碼中標記了從TLE到AC過程修改的關鍵一步，看樣子應該是數組作為函數參數傳遞時的細節問題，不過還是不明白，如有那位大神明白個中緣由，還望不吝賜教！！！
問題終於解決了，原來是在循環中重復調用 strlen( ) 函數導致了TLE，多謝各位熱心朋友的幫助！
注意：若要遍歷一個字符數組 str 時要先用一個變量記下 strlen(str) 的值，避免在循環中不停地調用 strlen( )
*/
題目大意：先給出一些單詞，然後給出一片文章，統計文章中出現的單詞數，這裡的每個單詞只統計一次。
[cpp]
#include"iostream"
#include"string"
#include"queue"
using namespace std;
char s[1000001],p[55] ;
//結點結構
struct Node
{
int cnt ;
Node *fail ;
Node *next[26] ;
};
Node *root = new Node ;
//初始化結點
void init(Node *t)
{
memset(t->next,NULL,sizeof(t->next)) ;
t->cnt = 0 ;
t->fail = NULL ;
}
//插入新單詞
void insert(char *str)
{
int i=0,k ;
Node *p = root ;
Node *newnode ;
while(str[i]){ //若用 for(i=0;i<strlen(str);i++) 一定先記下 strlen(str) 的值，防止TLE
k = str[i] - 'a' ;
if(p->next[k] == NULL){
newnode = new Node ;
init(newnode) ;
p->next[k] = newnode ;
p = newnode ;
}
else{
p = p->next[k] ;
}
i++;
}
p->cnt ++;
}
//確定fail指針
void makeFail()
{
Node *front ;
queue<Node *>q ;
q.push(root) ;
while(!q.empty()){
front = q.front() ;
q.pop() ;
for(int i = 0;i < 26;i++){
if(front->next[i] != NULL){ //父結點有孩子i，則找孩子i的fail指針
if(front == root)
front->next[i]->fail = root ;//與根結點相連的結點的fail指針都指向根結點
else{
Node *temp = front ;
while(temp->fail != NULL){ //父結點fail指針非空
if(temp->fail->next[i] != NULL){ //父結點fail指針指向的結點有孩子i
front->next[i]->fail = temp->fail->next[i] ;
break ;
}
temp = temp->fail ;//父結點向上轉移
}
if(temp->fail == NULL)
front->next[i]->fail = root ;
}
q.push(front->next[i]) ;//找到孩子i的fail指針後將孩子i加入隊列
}
}
}
}
//在文章中搜索單詞
int search(char *str)
{
Node *p = root ;
Node *temp = NULL ;
int i=0,k,ans = 0 ;
while(str[i]){
k=str[i] - 'a' ;
while(p != root && p->next[k] == NULL){
p = p->fail ;
}
if(p->next[k] != NULL){//p記錄當前位置最長的後綴匹配，下次從該支繼續匹配
p = p->next[k] ;
temp = p ; //用temp繼續找當前位置較短的後綴匹配
while(temp != root && temp->cnt != -1){
ans += temp->cnt ;//注意一定是+=，而不能直接++，因為cnt可能為0
temp->cnt = -1 ;
temp = temp->fail ;
}
}
i++;
}
return ans ;
}
//釋放內存
void freedom(Node *p)
{
for(int i = 0;i < 26;i++){
if(p->next[i] != NULL)
freedom(p->next[i]) ;
}
delete p ;
}
int main()
{
int t,k,i,ans ;
scanf("%d",&t) ;
while(t--){
init(root) ;
scanf("%d",&k) ;
getchar();
while(k--){
gets(p) ;
insert(p) ;
}
makeFail() ;
gets(s) ;
ans = search(s) ;
printf("%d\n",ans) ;
for(i = 0;i < 26;i ++){//注意root不能刪除
if(root->next[i] != NULL)
freedom(root->next[i]) ;
}
}
delete root ;
return 0 ;
}
#include"iostream"
#include"string"
#include"queue"
using namespace std;
char s[1000001],p[55] ;
//結點結構
struct Node
{
int cnt ;
Node *fail ;
Node *next[26] ;
};
Node *root = new Node ;
//初始化結點
void init(Node *t)
{
memset(t->next,NULL,sizeof(t->next)) ;
t->cnt = 0 ;
t->fail = NULL ;
}
//插入新單詞
void insert(char *str)
{
int i=0,k ;
Node *p = root ;
Node *newnode ;
while(str[i]){ //若用 for(i=0;i<strlen(str);i++) 一定先記下 strlen(str) 的值，防止TLE
k = str[i] - 'a' ;
if(p->next[k] == NULL){
newnode = new Node ;
init(newnode) ;
p->next[k] = newnode ;
p = newnode ;
}
else{
p = p->next[k] ;
}
i++;
}
p->cnt ++;
}
//確定fail指針
void makeFail()
{
Node *front ;
queue<Node *>q ;
q.push(root) ;
while(!q.empty()){
front = q.front() ;
q.pop() ;
for(int i = 0;i < 26;i++){
if(front->next[i] != NULL){ //父結點有孩子i，則找孩子i的fail指針
if(front == root)
front->next[i]->fail = root ;//與根結點相連的結點的fail指針都指向根結點
else{
Node *temp = front ;
while(temp->fail != NULL){ //父結點fail指針非空
if(temp->fail->next[i] != NULL){ //父結點fail指針指向的結點有孩子i
front->next[i]->fail = temp->fail->next[i] ;
break ;
}
temp = temp->fail ;//父結點向上轉移
}
if(temp->fail == NULL)
front->next[i]->fail = root ;
}
q.push(front->next[i]) ;//找到孩子i的fail指針後將孩子i加入隊列
}
}
}
}
//在文章中搜索單詞
int search(char *str)
{
Node *p = root ;
Node *temp = NULL ;
int i=0,k,ans = 0 ;
while(str[i]){
k=str[i] - 'a' ;
while(p != root && p->next[k] == NULL){
p = p->fail ;
}
if(p->next[k] != NULL){//p記錄當前位置最長的後綴匹配，下次從該支繼續匹配
p = p->next[k] ;
temp = p ; //用temp繼續找當前位置較短的後綴匹配
while(temp != root && temp->cnt != -1){
ans += temp->cnt ;//注意一定是+=，而不能直接++，因為cnt可能為0
temp->cnt = -1 ;
temp = temp->fail ;
}
}
i++;
}
return ans ;
}
//釋放內存
void freedom(Node *p)
{
for(int i = 0;i < 26;i++){
if(p->next[i] != NULL)
freedom(p->next[i]) ;
}
delete p ;
}
int main()
{
int t,k,i,ans ;
scanf("%d",&t) ;
while(t--){
init(root) ;
scanf("%d",&k) ;
getchar();
while(k--){
gets(p) ;
insert(p) ;
}
makeFail() ;
gets(s) ;
ans = search(s) ;
printf("%d\n",ans) ;
for(i = 0;i < 26;i ++){//注意root不能刪除
if(root->next[i] != NULL)
freedom(root->next[i]) ;
}
}
delete root ;
return 0 ;
}
