Simpsons’ Hidden Talents

clinton
homer
riemann
marjorie

0
rie 3

这题碰到了一些莫名其妙的问题，next数组本是记录模式串本身的匹配信息，我想着能不能用在两个不同的串上，然后就试验了一下，结果能想到的测试数据都能通过，但是就是WA，至今不知道错在哪里。

题意：给定两个串，求第二个串的后缀跟第一个串的前缀能匹配的最大长度并输出这个匹配串。

题解：在网上看到一种思路是将第一个串之后添加一个特殊字符，再把第二个串粘在第一个串后面，然后对这个新串求next数组，最终next[len]即为所求。

#include <stdio.h>
#include <string.h>
#define maxn 50002

char str1[maxn << 1], str2[maxn];
int ans, next[maxn << 1], len2;

void getNext()
{
	int i = 0, j = -1;
	next[0] = -1;
	while(str1[i]){
		if(j == -1 || str1[i] == str1[j]){
			++i; ++j;
			next[i] = j;
		}else j = next[j];
	}
	str1[ans = next[i]] = '\0';	
}

int main()
{	
	//freopen("stdin.txt", "r", stdin);
	while(scanf("%s%s", str1, str2) == 2){
		strcat(str1, " ");
		strcat(str1, str2); getNext();
		ans ? printf("%s %d\n", str1, ans) : printf("0\n");
	}
}

放一个典型的错误代码，能想到的测试数据都通过了，但是提交就WA。不知道为什么。

#include <stdio.h>
#define maxn 50002

char str1[maxn], str2[maxn] = {' '};
int ans, next[maxn];

void getNext()
{
    int i = 0, j = -1;
    next[0] = -1;
    while(str2[i]){
        if(j == -1 || str2[i] == str1[j]){
            ++i; ++j;
            next[i] = j;
        }else j = next[j];
    }
    str1[ans = next[i]] = '\0';
}

int main()
{    
    //freopen("stdin.txt", "r", stdin);
    while(scanf("%s%s", str1, str2 + 1) == 2){
        getNext();
        ans ? printf("%s %d\n", str1, ans) : printf("0\n");
    }
}

另外一个不知道错哪里的代码：

#include <stdio.h>
#define maxn 50002

char str1[maxn], str2[maxn] = {' ', ' '};
int ans, next[maxn];

void getNext()
{
    int i = 0, j = -1;
    next[0] = -1;
    while(str2[i]){
        if(j == -1 || str2[i] == str1[j]){
            ++i; ++j;
            next[i] = j;
        }else j = next[j];
    }
    str1[ans = next[i]] = '\0';
}

int main()
{    
    //freopen("stdin.txt", "r", stdin);
    while(scanf("%s%s", str1, str2 + 2) == 2){
        getNext();
        ans ? printf("%s %d\n", str1, ans) : printf("0\n");
    }
}

HDU2594 Simpsons’ Hidden Talents 【KMP】,布布扣,bubuko.com

HDU2594 Simpsons’ Hidden Talents 【KMP】

原文：http://blog.csdn.net/chang_mu/article/details/37915495