题目描述

We consider strings consisting of lowercase letters of the English alphabet in this problem.

An initial fragment of a given string is called its prefix.

A final (terminal) fragment of a given string is called its suffix.

In particular, the empty string is both a prefix and a suffix of any string.

Two strings are cyclically equivalent if one of them can be obtained from another by moving its certain suffix from the end of the string to its beginning.

For example, the strings and are cyclically equivalent, whereas the strings and are not.

In particular, every string is cyclically equivalent to itself.

A string consisting of letters is given.

We are looking for its prefix and suffix of equal length such that:

and are cyclically equivalent, the common length of and does not exceed (i.e., the prefix and the suffix do not overlap in ), and the common length of and is maximized.

对于两个串S1、S2，如果能够将S1的一个后缀移动到开头后变成S2，就称S1和S2循环相同。例如串ababba和串abbaab是循环相同的。

给出一个长度为n的串S，求满足下面条件的最大的L：

S的L前缀和S的L后缀是循环相同的。

输入输出格式

输入格式：

The first line of the standard input contains a single integer () denoting the length of the string .

The second line of input contains the string itself, consisting of lowercase letters of the English alphabet.

In tests worth 30% of the points the condition holds in addition.

In tests worth 50% of the points the condition holds in addition.

输出格式：

Your program should print a single integer in the first and only line of the standard output, namely the common length of the prefix and the suffix that we are looking for.

输入输出样例

输入样例#1：复制

15
ababbabababbaab

输出样例#1：复制

说明

对于两个串S1、S2，如果能够将S1的一个后缀移动到开头后变成S2，就称S1和S2循环相同。例如串ababba和串abbaab是循环相同的。

给出一个长度为n的串S，求满足下面条件的最大的L：

S的L前缀和S的L后缀是循环相同的。

首先分析本题性质：等价于找出一个前缀和一个后缀使它们能被拆成两个字符串s1、s2，且分别表示为s1 + s2和s2 + s1

那么问题就简单了，我们只需要对每一个位置i处理出(i, n - i + 1)这段区间内最长的相同前后缀F(i)，最后枚举一下即可。

暴力求是O(N)的，但是观察到如果(i + 1, n - i)处的相同前后缀确定为F(i + 1)，那么一定有F(i) <= F(i + 1) + 2。为什么呢？因为考虑(i + 1, n - i)相同的一段前后缀，如果同时向左右扩一位后能产生比F(i + 1) + 2大的答案，那么大概会是这样：

X abc o..sA..o o..sB..o abc X

并且由于>F(i + 1) + 2，sA、sB的长度都大于1 。因此一定有：X abc 为sB一段前缀。 abc X为sA一段后缀.并且sA除abc X一段和sB除X abc一段的字符串完全一样。那么因此F(i + 1)一定可以扩大至这段一样的字符串。就得证了。
(看不懂网上的证明，推了半天……)

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 2e6 + 5;
const int base = 741, mod = 19260817;
int hsh[maxn], pow[maxn], inv[maxn], f[maxn], n, p, ans, bi;
char s[maxn];

int fpow(int a, int b, int p) {
	int ans = 1;
	while(b) {
		if(b & 1) ans = 1ll * ans * a % p;
		b >>= 1, a = 1ll * a * a % p;
	}
	return ans;
}

int GetHsh(int l, int r) {
	return ((1ll * (hsh[r] - hsh[l - 1]) * inv[l - 1]) % mod + mod) % mod;
}

int main() {
	scanf("%d", &n), scanf("%s", s + 1);
	pow[0] = 1, inv[0] = 1, bi = fpow(base, mod - 2, mod);
	for(register int i = 1; i <= n; ++i)
		pow[i] = 1ll * pow[i - 1] * base % mod;
	for(register int i = 1; i <= n; ++i)
		inv[i] = 1ll * inv[i - 1] * bi % mod;
	for(register int i = 1; i <= n; ++i) {
		hsh[i] = (hsh[i - 1] + 1ll * s[i] * pow[i] % mod) % mod;
	}
	for(register int i = n / 2; i >= 1; --i) {
		for(register int j = f[i + 1] + 2; j >= 0; --j) {
			if(i + j > n / 2) continue;
			if(GetHsh(i, i + j) == GetHsh(n - i - j + 1, n - i + 1)) 
				{f[i] = j + 1; break;}
		}	
	}
	for(register int i = 1; i <= n / 2; ++i) 
		if(GetHsh(1, i) == GetHsh(n - i + 1, n))
			ans = max(i + f[i + 1], ans);
	printf("%d\n", ans);
	return 0;
}

Rockdu's Blog