http://www.cnblogs.com/kuangbin/p/3164106.html kuangbin的博客

第一段代码基本是COPY kuangbin的..

1、    最基本的入门题了

就是求目标串中出现了几个模式串。

很基础了。使用一个int型的end数组记录，查询一次。

//======================// HDU 2222// 求目标串中出现了几个模式串//输入 //1//5//she//he//say//shr//her//yasherhs //====================#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;struct Trie{	int next[500010][26],fail[500010],end[500010];	int root,L;	int newnode()	{		for(int i=0;i<26;i++)			next[L][i]=-1;		end[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
          

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; //第一层的失败指针指向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 { 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

< 26;j++) printf("%2d",next[i][j]); printf("]\n"); } } };char s[300];char buff[1000005]; Trie ac;void input(){ int n; cin>>n; ac.init(); for(int i=1;i<=n;i++) { scanf("%s",s); ac.insert(s); } ac.build();}int main(){ int T; cin>>T; while(T--) { input(); scanf("%s",buff); printf("%d\n",ac.query(buff)); }}