首页 > 其他 > 详细

hdu 2594 Simpsons’ Hidden Talents

时间:2017-06-27 18:13:52      阅读:252      评论:0      收藏:0      [点我收藏+]

题意是求第一个字符的前缀和后一个字符串的后缀最大的公共序列,并输出。。

将两个字符串合并,求出kmp中的next数组即可。但要注意不要大于某个字符串的长度。

#include <stdio.h>
#include <string.h>


const int N = 50005;
#define min(a,b) ((a)<(b)?

(a):(b))
char s1[N], s2[N], s3[N * 2];
int next[N * 2];




void get_next(char *seq, int m) {
next[0] = -1;
int j = next[0];
for (int i = 1; i < m; i++) {
while (j >= 0 && seq[i] != seq[j + 1]) j = next[j];
if (seq[i] == seq[j + 1]) j++;
next[i] = j;
}
}




int main() {
while (~scanf("%s%s", s1, s2)) {
int len1 = strlen(s1), len2 = strlen(s2);
strcpy(s3, s1); strcpy(s3 + len1, s2);
int len3 = strlen(s3);
get_next(s3, len3);
int ans = min(min(len1, len2), next[len3 - 1] + 1);
for (int i = 0; i < ans; i++)
printf("%c", s1[i]);
if (ans) printf(" ");
printf("%d\n", ans);
}
return 0;
}

hdu 2594 Simpsons’ Hidden Talents

原文:http://www.cnblogs.com/lytwajue/p/7086299.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!