hdu 2222 AC 자동 동기

http://acm.hdu.edu.cn/showproblem.php?pid=2222
/*
AC 자동 동기 템 플 릿 문제,시간 초과 횟수 20+,반나절 을 고 쳐 마침내 AC 가 되 었 습 니 다.코드 에 TLE 에서 AC 까지 과정 을 수정 하 는 관건 적 인 단 계 를 표 시 했 습 니 다.보아하니 배열 이 함수 매개 변수 로 전달 할 때의 세부 적 인 문제 인 것 같 습 니 다.그러나 잘 모 르 겠 습 니 다.만약 에 그 큰 신 이 그 이 유 를 알 고 아 낌 없 는 가르침 을 바 랍 니 다!
문 제 는 마침내 해결 되 었 습 니 다.순환 에서 strlen()함 수 를 중복 호출 하여 TLE 를 만 들 었 습 니 다.여러분 의 따뜻 한 친구 들 의 도움 에 감 사 드 립 니 다!
메모:한 문자 배열 str 를 옮 겨 다 닐 때 하나의 변수 로 strlen(str)의 값 을 기록 하고 순환 중 에 strlen()을 계속 호출 하지 않도록 해 야 합 니 다.
*/
제목 의 대의:먼저 단 어 를 제시 한 다음 에 문장 한 장 을 제시 하고 문장 에 나타 난 단어 수 를 통계 하 며 여기 있 는 모든 단 어 는 한 번 만 통계 한다.

#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
",ans) ;
		for(i = 0;i < 26;i ++){//  root    
			if(root->next[i] != NULL)
				freedom(root->next[i]) ;
		}
	}
	delete root ;
	return 0 ;
}