UVA1449 Dominating Patterns

题目描述

有N个由小写字母组成的模式串以及一个文本串T。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串T中出现的次数最多。

输入输出格式

输入格式：

输入含多组数据。

每组数据的第一行为一个正整数N，表示共有N个模式串，1≤N≤150。

接下去N行，每行一个长度小于等于70的模式串。下一行是一个长度小于等于10^6 的文本串T.

输入结束标志为N=0。

输出格式：

对于每组数据，第一行输出模式串最多出现的次数，接下去若干行每行输出一个出现次数最多的模式串，按输入顺序排列。

输入输出样例

输入样例：

2

aba

bab

ababababac

6

beta

alpha

haha

delta

dede

tata

dedeltalphahahahototatalpha

0

输出样例：

4

aba

2

alpha

haha

 挺有意思的的一道题，由于模板链（我是不是学生物学多了）模式串有很多，所以我们可以使用AC自动机来处理，然而模式串直接可能有重复，所以我们只需要在重复的模式串之间取一个就好了，为了方便，可以直接在trie树上统计每一个模式串最后出现的位置，然后就是AC自动机模板了。

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<string>

 #include<cstring>

 #include<map>

 #include<queue>

 #include<stack>

 #include<algorithm>

 #include<vector>

 #define man 1000005

 #define maxn 155

 using namespace std;

 inline int read()

 {

     char c=getchar();

     int res=,x=;

     while(c<''||c>'')

     {

         if(c=='-')

         x=-;

         c=getchar();

     }

     while(c>=''&&c<='')

     {

         res=res*+(c-'');

         c=getchar();

     }

     return res*x;

 }

 int n,tot,ans;

 int co[],f[],nt[],tree[][];

 char b[][],a[man];

 queue<int>q;

 void trie(char *s,int num)

 {

     int len=strlen(s),u=;

     for(register int i=;i<len;i++)

     {

         int c=s[i]-'a';

         if(!tree[u][c])

         {

             tree[u][c]=++tot;

         }

         u=tree[u][c];

     }

     co[u]=num;//只需要统计每一个字符串的结尾就可以去重

 }

 void bfs()

 {

     for(register int i=;i<;i++)

     tree[][i]=;

     nt[]=;q.push();

     while(q.size())

     {

         int u=q.front();q.pop();

         for(register int i=;i<=;i++)

         {

             if(!tree[u][i])

             tree[u][i]=tree[nt[u]][i];

             else

             {

                 int v=tree[u][i];

                 q.push(v);

                 nt[v]=tree[nt[u]][i];

             }

         }

     }

 }

 void find(char *s)

 {

     int len=strlen(s),u=,k;

     for(register int i=;i<len;i++)

     {

         int c=s[i]-'a';

         k=tree[u][c];

         while(k>)

         {

             f[co[k]]++;

             k=nt[k];

         }

         u=tree[u][c];

     }

 }

 int main()

 {

     while()

     {

         n=read();

         if(n==) break;

         memset(co,,sizeof(co));

         memset(f,,sizeof(f));

         memset(nt,,sizeof(nt));

         memset(tree,,sizeof(tree));

         tot=,ans=;

         for(register int i=;i<=n;i++)

         {

             scanf("%s",b[i]);

             trie(b[i],i);

         }

         scanf("%s",a);

         bfs();

         find(a);

         for(register int i=;i<=n;i++)

         ans=max(ans,f[i]);

         printf("%d\n",ans);

         for(register int i=;i<=n;i++)

         {

             if(f[i]==ans)

             printf("%s\n",b[i]);

         }

     }

     return ;

 }