BZOJ 1355 [Baltic2009] Bazinga

题面

【题目描述】

对于给定的n个字符串S1,S2……，Sn，标号为1到n，请你找出一个最大的i使得标号小于i的字符串中存在一个不是i的子串。

【输入描述】：

第一行包括一个整数t(1<=t<=50)代表测试数据的组数。

对于每组测试数据，第一行一个整数n(1<=n<=2000)。接下来n行代表S1,S2……Sn。

所有字符串都是小写字母，字符串长度不超过2000。

【输出描述】

对于每组测试数据，输出你能求到的最大标号，如果不存在，输出-1。

【样例输入】:

4 5

ab

abc

zabc

abcd

zabcd

4

you

lovinyou

aboutlovinyou

allaboutlovinyou

5

de

def

abcd

abcde

abcdef

3

a

ba

ccc

【样例输出】：

Case #1: 4

Case #2: -1

Case #3: 4

Case #4: 3

题解

KMP的应用之一找循环节.

假设字符串的最后一位为\(n\), 则循环节长度为\(n-next[n]\).

无编译1A.

#include <cstdio>

const int L = (int)1e6;

int main()

{

	int n;

	scanf("%d\n", &n);

	static char str[L];

	scanf("%s", str);

	static int nxt[L];

	nxt[0] = -1;

	int p = nxt[0];

	for(int i = 1; i < n; ++ i)

	{

		for(; ~ p && str[p + 1] ^ str[i]; p = nxt[p]);

		nxt[i] = str[p + 1] == str[i] ? ++ p : p;

	}

	printf("%d", n - 1 - nxt[n - 1]);

}

巴特西