Bazinga HDU 5510 Bazinga(双指针)

解法：对于串i来说，如果串i是不符合的，那么代表串i之前的字符串都是i的子串，那么我们求一个新的i(定义为ti)，如果i是ti 的子串，那么串i之前的字符串都没必要再匹配了，如果不是，ti就是符合要求的答案之一

#include <cstdio>

#include <iostream>

#include <cstring>

using namespace std;

const int N=2005;

char a[505][N];

int f[505][N];

void getFail(int id)

{

    f[id][0]=f[id][1]=0;

    int m=strlen(a[id]);

    for(int i=1;i<m;i++)

    {

        int j=f[id][i];

        while(j&&a[id][i]!=a[id][j]) j=f[id][j];

        f[id][i+1]=a[id][i]==a[id][j]?j+1:0;

    }

}

int find(int id1,int id2)

{

    int j=0,n=strlen(a[id1]),m=strlen(a[id2]);

    for(int i=0;i<n;i++)

    {

        while(j&&a[id2][j]!=a[id1][i]) j=f[id2][j];

        if(a[id2][j]==a[id1][i]) j++;

        if(j==m) return i-m+2;

    }

    return -1;

}

int main()

{

    int T;

    scanf("%d",&T);

    int ca=0;

    while(T--)

    {

        int n;

        scanf("%d",&n);

        for(int i=1;i<=n;i++){

                scanf("%s",a[i]);

                getFail(i);

        }

        int flag=0,ans=-1;

        int l=1,r=1;

        while(r<=n){

            while(l<r){

                if(find(r,l)!=-1) l++;

                else{

                    ans=r;

                    break;

                }

            }

            r++;

        }

        printf("Case #%d: %d\n",++ca,ans);

    }

    return 0;

}

巴特西

Bazinga HDU 5510 Bazinga(双指针)

Bazinga HDU 5510 Bazinga(双指针)

最新文章

热门文章