Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

两个错误

Posted by ProgrammingEveryday at 2012-09-10 10:40:18 on Problem 1226
In Reply To:Re:用的kmp,在航电交过了 ,在这里却过不了,哪位好心人能帮看看啊!不胜感机 Posted by:19901011 at 2011-04-14 10:41:42
第一个: 在查找反串是否存在时,你的j 没有初始化,(j = -1;)
第二个: 你没有处理字符串就只有一个的情况。
#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;
        }
		j = -1;  // 初始化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]);
        }
        if (n == 1)  // 处理字符串只有一个的情况
		{
			printf ("%d\n", strlen (str[0]));
			continue;
		}
        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);
    }
}
你查找最长子串的方式比我的要好,比我的快了几十MS;
我的是一个个枚举了所有子串。 

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator