poj 3450 Corporate Identity (KMP+最长公共子串)

题目大意: 给定n个字符串，找出最长的公共子串，若长度小于3输出IDENTITY LOST

解题思路: 选出长度最短的字符串，枚举它的子串

把它的子串分别与其余的n-1个字符串匹配

字符串长度越短它的子串就越少，枚举量越少

枚举子串的顺序从大到小，能够匹配就退出输出答案

如果从小到大枚举则需要枚举所有符合情况的子串，耗费时间

代码:

//Final   找最长的公共子串，注意 less than 3，是小于3，不等于  
#include <stdio.h>  
#include <algorithm>  
#include <string.h>  
#include <stdlib.h>  
#define Max 4010  
#define INF 0x3f3f3f3f  
using namespace std;  
int Long[Max],Next[202];  
char ch[Max][202];  
struct snode{  
    char ch3[202];  
}chtemp[Max];  
  
bool cmp(struct snode a,struct snode b)  
{  
    int temp=strcmp(a.ch3,b.ch3);  
    if(temp>=0)  
        return 0;  
    return 1;  
}  
  
void Get_next(char ch1[],int Tlen)  
{  
    int i=0,j=-1;  
    Next[0]=-1;  
    while(i<Tlen)  
    {  
        if(j==-1||ch1[j]==ch1[i])  
        {  
            i++; j++;  
            Next[i]=j;  
        }  
        else  
            j=Next[j];  
    }  
}  
  
int Kmp(char ch1[],int ii,int Tlen)  
{  
    int i=-1,j=-1;  
    while(i<Long[ii]&&j<Tlen)  
    {  
        if(j==-1||ch1[j]==ch[ii][i])  
        {  
            i++; j++;  
        }  
        else  
            j=Next[j];  
    }  
    if(j>=Tlen)  
        return 1;  
    return 0;  
}  
  
int main()  
{  
    char ch1[202];  
    int min,mini,i,j,j1,j2,temp,n,m,k,pd,pdi,End;  
    while(scanf("%d",&n)!=EOF&&n)  
    {  
        min=INF;  
        memset(ch,0,sizeof(ch));  
        for(i=1;i<=n;i++)  
        {  
            scanf("%s",ch[i]);  
            temp=strlen(ch[i]);  
            Long[i]=temp;  
            if(temp<min)  
                min=temp,mini=i;  
        }  
        for(i=Long[mini],pd=0,m=0;i>=1;i--)  
        {  
            End=Long[mini]-i;  
            for(j=0;j<=End;j++)  
            {  
                memset(ch1,0,sizeof(ch1));  
                for(j1=j,j2=0;j2<i;j2++,j1++)  
                {  
                    ch1[j2]=ch[mini][j1];  
                }  
                ch1[j2]='\0';  
                memset(Next,0,sizeof(Next));  
                Get_next(ch1,i);  
                for(j1=1,k=1;j1<=n;j1++)  
                {  
                    if(j1==mini)  
                        continue;  
                    if(Kmp(ch1,j1,i))  
                    {  
                        k++;  
                    }  
                    else  
                        break;  
                }  
                if(k==n)  
                {  
                    strcpy(chtemp[m++].ch3,ch1);  
                    pd=1;  
                    pdi=i;  
                }  
            }  
            if(pd==1)  
            {  
                sort(chtemp,chtemp+m,cmp);  
                printf("%s\n",chtemp[0].ch3);  
                break;  
            }  
        }  
        if(pd==0)  
            printf("IDENTITY LOST\n");  
    }  
    return 0;  
}

补充：软件开发 , C++ ,