poj--3450 KMP求多个字符串的最长公共子串

思路与前面的3080一样

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

char str1[220],str2[220];
int next[220],n;
char ch[4400][220];

void GetNext()
{
    int j=0;
    int len=strlen(str2+1);
    next[1]=0;
    for(int i=2;i<=len;i++)
    {
        while(j>0&&str2[j+1]!=str2[i])
             j=next[j];
        if(str2[j+1]==str2[i])
             j++;
        next[i]=j;
    }
}

int KMP()
{
    GetNext();
    int j=0;
    int m=strlen(str2+1);
    int len=strlen(str1+1);
    for(int i=1;i<=len;i++)
    {
        while(j>0&&str2[j+1]!=str1[i])
            j=next[j];
        if(str2[j+1]==str1[i])
            j++;
        if(j==m)
            return 1;
    }
    return 0;
}

void solve(char *ans)
{
     int d=strlen(ch[1]);
     for(int i=0;i<d;i++)
     {
         int cnt=i;
         while(cnt<d)
         {
             int ii;
             for(int j=i;j<=cnt;j++)
                str2[j-i+1]=ch[1][j];
             str2[cnt+2-i]=‘\0‘;///记得最后一位加上字符串结束标志
             for(ii=2;ii<=n;ii++)
             {
                 strcpy(str1+1,ch[ii]);
                 if(KMP()==0)
                    break;
             }
             if(ii>n)
             {
                 if(strlen(str2+1)>strlen(ans+1))
                    strcpy(ans+1,str2+1);
                 else if (strlen(str2+1)==strlen(ans+1))
                 {
                    if(strcmp(ans+1,str2+1)>0)
                        strcpy(ans+1,str2+1);
                 }
                 cnt++;
             }
             else
                break;
         }
     }
     if(strlen(ans+1)==0)
         printf("IDENTITY LOST\n");
     else
         printf("%s\n",ans+1);
}

int main()
{
    while(scanf("%d",&n)&&n)
    {
        char ans[220];
        ///每次都必须要将ans数组清空,否则上次的答案会影响下次
        memset(ans,‘\0‘,sizeof(ans));
        for(int i=1;i<=n;i++)
            scanf("%s",ch[i]);
        solve(ans);
    }
  return 0;
}