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