hdu 2594 Simpsons’ Hidden Talents

发布时间:2016-12-11 17:53:35 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"hdu 2594 Simpsons’ Hidden Talents",主要涉及到hdu 2594 Simpsons’ Hidden Talents方面的内容,对于hdu 2594 Simpsons’ Hidden Talents感兴趣的同学可以参考一下。

        hdu 2594 Simpsons’ Hidden Talents         求第一个字符串StrA的前缀和第二个字符串strB的后缀的最大长度.         只要把strA当做模式串去匹配strB就可以啦, 不过还要注意被匹配串strB的长度哦。        例如 strA = 'abcabcabcabc', strB = 'abcabcabcabcabc' 答案却是 abc 3... #include <stdio.h> #include <string.h> #define MAX 50005 char name[MAX], talentName[MAX]; int next[MAX]; void getNext(char* str, int* next) { int len; int j, k; j = 0; k = -1; next[0] = k; len = strlen(str) - 1; while (j < len) { if (k == -1 || str[k] == str[j]) { ++k, ++j; if (str[k] == str[j]) { next[j] = next[k]; } else { next[j] = k; } } else { k = next[k]; } } } int kmp(char* strA, char* strB) { int lenA, lenB; int i, j; i = j = 0; lenA = strlen(strA); lenB = strlen(strB); getNext(strB, next); if (lenA > lenB) { i = lenA - lenB; } while (i < lenA) { if (j == -1 || strA[i] == strB[j]) { ++j, ++i; } else { j = next[j]; } } return j; } int main() { int matchNum; int i; while (scanf("%s%s", name, talentName) != EOF) { matchNum = kmp(talentName, name); if (matchNum == 0) { printf("0\n"); } else { for (i = 0; i < matchNum; i++) { printf("%c", name[i]); } printf(" %d\n", matchNum); } } return 0; }

上一篇:开发笔记 那些年追过的图片(四):改变相册里的英文变成中文
下一篇:IOS上AudioSession设置, 切换扬声器和听筒详解

相关文章

相关评论