#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
int p[105], l[105];
char pat[105],     str[102][105];
int lpat, n;
void next()
{
    int i, j;
    p[0] = -1;
    j = -1;
    for (i=1; i<l[0]; i++)
    {
        while (j>=0 && pat[j+1] != pat[i])
            j = p[j];
        if (pat[j+1] == pat[i])
            j++;
        p[i] = j;
    }
    return ;
}
int kmp()
{
    int i, j, k, m, Maxl;
    Maxl  = 101;
    next();
    for (i=1; i<n; i++)
    {
        j = -1; m = -1;
        for (k=0; k<l[i]; k++)
        {
            while (j>=0 && str[i][k] != pat[j+1])
               j = p[j];
            if (str[i][k] == pat[j+1])
               j++;
            if (j>m)
            m = j;
        }
        for (k=l[i]-1; k>=0; k--)
        {
            while (j>=0 && str[i][k] != pat[j+1])
              j = p[j];
            if (str[i][k] == pat[j+1])
            j++;
            if (j>m)
            m = j;
        }
        if (m<Maxl)
        Maxl = m;
    }
    return Maxl+1;
}
int main()
{
    int t, i, value, ans;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        for (i=0; i<n; i++)
        {
            scanf("%s", str[i]);
            l[i] = strlen(str[i]);
        }
        //cout<<"AAAAAAA"<<endl;
        ans = 0;

        for (i=0; i<l[0]; i++)
        {
            strcpy(pat, str[0]+i);
            lpat = l[0] - i;
            value = kmp();
            if (value > ans)
               ans = value;
        }
        printf("%d\n", ans);
    }
}

• Re:用的kmp,在航电交过了 ,在这里却过不了,哪位好心人能帮看看啊!不胜感机 (13) 19901011 2011-04-11 22:19:29
  • Re:用的kmp,在航电交过了 ,在这里却过不了,哪位好心人能帮看看啊!不胜感机 (27) 19901011 2011-04-14 10:41:42
    • 两个错误 (1820) ProgrammingEveryday 2012-09-10 10:40:18