Blue Jeans POJ

题目链接

题意：求n个串的公共子串

思路：由于数据比较小，所以可以暴力枚举第一个串的所有子串，进行kmp匹配。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char ans[100];
int Next[100];
char s[100][100];
void getNext(char w[],int m){
    int i = -1,j = 0;
    memset(Next,0,sizeof(Next));
    Next[0] = -1;
    while(j < m){
        if(i == -1 || w[i] == w[j]){
            i++,j++;
            Next[j] = i;
        }
        else
            i = Next[i];
    }
}
bool kmp(char w[],int m,char s[],int n){
    int i = 0,j = 0;
    getNext(w,m);
    while(j < n){
        if(i == -1 || w[i] == s[j])
            i++,j++;
        else
            i = Next[i];
        if(i >= m)
            return true;
    }
    return false;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        memset(ans,0,sizeof(ans));
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%s",s[i]);
        }
        int len=strlen(s[0]);
        char w[100];
        for(int i=0;i<len;i++)
        {
            int cnt=0;
            w[cnt++]=s[0][i];
            for(int j=i+1;j<len;j++)
            {
                w[cnt++]=s[0][j];
                int flag=0;
                for(int k=1;k<n;k++)
                {
                    if(!kmp(w,cnt,s[k],strlen(s[k])))
                    {
                        flag=1;
                        break;
                    }    
                }
                if(flag==0)
                {
                    w[cnt]='';
                    if(cnt>strlen(ans))
                    {
                        
                        strcpy(ans,w);
                    }
                    else if(cnt==strlen(ans)&&strcmp(w,ans)<0)
                    {
                        strcpy(ans,w);
                    }
                }
            }
        
        }if(strlen(ans)<3)
        {
            printf("no significant commonalities
");
            continue;
        }
        printf("%s
",ans);
    }
}