【poj1226】Substrings

2015.04.15 16:58 Wed | 12次阅读 | 旧日oi | 固定链接 | 源码

Description
You are given a number of case-sensitive strings of alphabetic characters, find the largest string X, such that either X, or its inverse can be found as a substring of any of the given strings.
Input
The first line of the input contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case contains a single integer n (1 <= n <= 100), the number of given strings, followed by n lines, each representing one string of minimum length 1 and maximum length 100. There is no extra white space before and after a string.
Output
There should be one line per test case containing the length of the largest string found.
Sample Input
2
3
ABCD
BCDFF
BRCD
2
rose
orchid
Sample Output
2
2
题解
求多个串的最长公共子串,每个串可以倒过来看。
两种办法,一种暴力kmp,一种后缀数组,kmp 0ms,后缀数组375ms……
kmp就是怎么暴力怎么来吧,枚举长度,枚举在第一个串中的起始位置,搞出next数组,然后和剩下的正反各匹配一遍就行了

我的程序

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int T,n;
char str[101][101];
char str2[101][101];
int next[101];
char tmp[101];
void get_next(int l)
{
    next[0]=-1;
    int j=0,k=-1;
    while(j<l)
    {
        if(k==-1||tmp[j]==tmp[k])
        {
            j++;
            k++;
            next[j]=k;
        }
        else k=next[k];
    }
}
bool check(int n,int m)
{
    int i=0,j=0,l=strlen(str[n]);
    while(i<l)
    {
        if(j==-1||str[n][i]==tmp[j])
        {
            i++;
            j++;
        }
        else j=next[j];
        if(j==m) return 0;
    }
    return 1;
}
bool check2(int n,int m)
{
    int i=0,j=0,l=strlen(str2[n]);
    while(i<l)
    {
        if(j==-1||str2[n][i]==tmp[j])
        {
            i++;
            j++;
        }
        else j=next[j];
        if(j==m) return 0;
    }
    return 1;
}
int main()
{
    //freopen("kmp.in","r",stdin);
    cin>>T;
    for(int t=1;t<=T;t++)
    {
        cin>>n;
        int ans=0;
        for(int i=1;i<=n;i++) 
        {
            scanf("%s",str[i]);
            int l=strlen(str[i]);
            for(int j=0;j<l;j++)
            str2[i][l-1-j]=str[i][j];
        }
        int l1=strlen(str[1]),st;
        for(int len=l1;len;len--)
        {
            for(int i=0;i+len<=l1;i++) 
            {
                for(int j=0;j<len;j++) tmp[j]=str[1][i+j];
                get_next(len);
                st=1;
                for(int j=2;j<=n;j++)
                if(check(j,len)&&check2(j,len))
                {
                    st=0;
                    break;
                }
                if(st) { ans=len; break;}
            }
            if(ans) break;
        }
        cout<<ans<<endl;
    }
    return 0;
}
后缀数组
把所有串及其反串弄到一起,中间用分隔符分开,求出sah数组
然后二分长度l,在h数组中找连续的长度超过l的段,如果段中包含的点所对应的串的数量达到n,就说明有长度为l的公共子串,具体内容看代码吧
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define maxn 30001
using namespace std;
int T,n,len;
char s[101];
int a[30001];
int sa[maxn],val[maxn],cnt[maxn],_val[maxn],rank[maxn],h[maxn],stk[maxn],top;
int tmp[maxn],vis[maxn];
bool issame(int x,int y,int hl)
{
    return  val[x]==val[y]&&((x+hl>=len&&y+hl>=len)||(x+hl<len&&y+hl<len&&val[x+hl]==val[y+hl]));
}
void get_sa(int lim)
{
    int i,j,k,hl;
    for(i=0;i<lim;i++) cnt[i]=0;
    for(i=0;i<len;i++) cnt[val[i]=a[i]]++;
    for(i=1;i<lim;i++) cnt[i]+=cnt[i-1];
    for(i=len-1;i>=0;i--)  sa[--cnt[val[i]]]=i;
    for(k=0;;k++)
    {
        top=0;hl=1<<k;
        for(i=0;i<len;i++) if(sa[i]+hl>=len) stk[++top]=sa[i];
        for(i=0;i<len;i++) if(sa[i]>=hl) stk[++top]=sa[i]-hl;
        for(i=0;i<lim;i++) cnt[i]=0;
        for(i=0;i<len;i++) cnt[val[i]]++;
        for(i=1;i<lim;i++) cnt[i]+=cnt[i-1];
        for(i=len;i;i--) sa[--cnt[val[stk[i]]]]=stk[i];
        for(i=lim=0;i<len;lim++)
        {
            for(j=i;j<len-1&&issame(sa[j],sa[j+1],hl);j++);
            for(;i<=j;i++) _val[sa[i]]=lim;
        }
        for(i=0;i<len;i++) val[i]=_val[i];
        if(lim==len) break;
    }
    for(i=0;i<len;i++)rank[sa[i]]=i;
    for(k=i=0;i<len;i++)
    {
        if(k) k--;
        if(!rank[i])continue;
        while(a[i+k]==a[sa[rank[i]-1]+k])k++;
        h[rank[i]]=k;
    }
}
bool check(int l)
{
    int tot=0;
    for(int i=1;i<len;i++)
    {
        if(h[i]<l)
        {
            memset(tmp,0,sizeof(tmp));
            tot=0;
            continue;
        }
        else
        {
            if(!tmp[vis[sa[i-1]]])
            {
                tmp[vis[sa[i-1]]]=1;
                tot++;
            }
            if(!tmp[vis[sa[i]]]) 
            {
                tmp[vis[sa[i]]]=1;
                tot++;
            }
            if(tot==n) 
            return 1;
        }
    }
    return 0;
}
void work()
{
    int ans=0;
    int l=1,r=100,mid;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(check(mid))
        {
            ans=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    cout<<ans<<endl;
}
int main()
{
    //freopen("sa.in","r",stdin);
    cin>>T;
    for(int i=1;i<=T;i++)
    {
        cin>>n;
        if(n==1)
        {
            scanf("%s",s);
            int l=strlen(s);
            cout<<l<<endl;
            continue;
        }
        int fengefu=150;
        len=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%s",s);
            int l=strlen(s);
            for(int j=0;j<l;j++) 
            {
                vis[len]=i;
                a[len++]=s[j];
            }
            a[len++]=++fengefu;
            for(int j=l-1;j>=0;j--) 
            {
                vis[len]=i;
                a[len++]=s[j];
            }
            a[len++]=++fengefu;
        }
        get_sa(300);    
        work();
    }   
}```