| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
两个错误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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator