[KMP][二分] POJ 3450

这个题有很多做法,目前先用二分+KMP过了,二分的原理是如果最大字串存在那么这个最大字串的字串也一定满足要求。难得1Y,明天用后缀数组尝试一下来填坑。。


//#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include
#define eps (1e-6)
using namespace std;
typedef long long LL;
const int maxn=2e2+5;
const int MOD=1e9+7;
const int INF=0x4f4f4f4f;

char y[4005][maxn],ma[maxn];
int nxt[maxn];
void kmp_pre(char * x,int m)
{
    int i,j;
    j=nxt[0]=-1;
    i=0;
    while(i=m)
        {
            return 1;
        }
    }
    return 0;
}
int t,l,r,tl,tmp,flag=0,mid,len[4005];
char tep[maxn];
int check(int k)
{
    int ans;
    ans=1;
    for (int i=0; i+k<=tl; i++)
    {
        char *x=ma+i;
        int j;
        for (j=1; j<=t; j++)
        {
            if(!KMP_Count(x,k,j,len[j]))
                break;
        }
        if(j>t)
            return 1;
    }
    return 0;
}
char ans[maxn],fuck[maxn];
void getans(int k)
{
    int flag=-1;
    ans[0]='z'+1;
    char * x;
    for (int i=0; i+k<=tl; i++)
    {
        x=i+ma;

        int j;
        for (j=1; j<=t; j++)
        {
            if(!KMP_Count(x,k,j,len[j]))
                break;
        }
        if(j>t)
        {
            strcpy(fuck,x);
            fuck[k]=0;
            if(strcmp(fuck,ans)<0)
            {
                strcpy(ans,fuck);
            }

        }
    }
    printf("%s\n",ans);
}

int main()
{
    //freopen("1.txt","r",stdin);
    //freopen("2.txt","w",stdout);

    while(~scanf("%d",&t)&&t)
    {
        tl=INF;
        flag=0;
        getchar();
        for (int i=1; i<=t; i++)
        {
            gets(y[i]);
            len[i]=strlen(y[i]);
            if(len[i]l)
        {
            mid=(r+l+1)>>1;
            if(check(mid))
                l=mid;
            else
                r=mid-1;
        }
        if(r!=0)
            getans(r);
        else
            printf("IDENTITY LOST\n");
    }
    return 0;
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据