Codeforces 126B（kmp）

要点

头尾的最长相同只要一个kmp即可得，于是处理中间部分
扫一遍记录一下前缀的每个位置是否存在一个中间串跟它相同，见代码
如果当前没有，接着用Next数组去一找即可

#include <cstdio>

#include <cstring>

const int maxn = 1e6 + 5;

char s[maxn];

int Next[maxn], Has[maxn], flag;

int main() {

	scanf("%s", s + 1);

	int n = strlen(s + 1);

	for (int i = 2, j = 0; i <= n; i++) {//kmp

		while (j && s[j + 1] != s[i])	j = Next[j];

		if (s[j + 1] == s[i])	j++;

		Next[i] = j;

		if (i < n)	Has[Next[i]] = 1;//不能是头和尾

	}

	for (flag = Next[n]; flag && !Has[flag]; flag = Next[flag]);//没有就接着找

	if (flag) {

		s[flag + 1] = 0;

		printf("%s\n", s + 1);

	} else {

		printf("Just a legend\n");

	}

	return 0;

}

巴特西

Codeforces 126B（kmp）

要点

最新文章

热门文章