返回全部题目

BUC3399K 下笔成章

题目描述

小 F 有一个字符串 $s$，她想知道是否存在这样一个子串 $t$，$t$ 既是 $s$ 的前缀，又是 $s$ 的后缀，同时在字符串中还出现过一次（在除前后缀以外出现，可能和前后缀有部分重合）。
假如存在这样的子串 $t$，请输出最长长度的 $t$，否则输出 I'll write one for you。

输入

小写字母组成的子串 $s$
$s$ 长度在 $[1,1e6]$ 间

输出

存在则输出 $t$，否则输出 I'll write one for you

样例输入

1
fixprefixixffix

样例输出

1
fix

比如我现在有一串字符串 fixprefixixffix，因为都是小写，我们可以将其转换为 $0\sim25$ 的数字，即 5,8,23,15,17,4,5,8,23,8,23,5,5,8,23。

勘误：尽量不要用 $0$，建议改为 $1\sim26$。

首先复习一下，如果我要多次查询连续几项的和，如第 $1\sim3$ 项元素之和，以及第 $7\sim9$ 项元素之和，应该怎样操作？

聪明的你知道，先预处理前缀和，得到 5,13,36,51,68,72,77,85,108,116,139,144,149,157,180，那么 sum[3]-sum[0]=36, sum[9]-sum[6]=36 即是结果，前缀和处理可以大大降低时间复杂度。

如果我问，哪些连续三项的和等于 36，你一定也能很快得出结果，是 $1\sim3,~7\sim9,~10\sim12,~13\sim15$ 这些，

我们发现，这里面有些恰好是 fix，但有些不是，比如 ixf，利用前缀和搜索是不可行的，因为就算这几项的和相同，字母也不一定相同。

有什么办法解决呢？

就拿阿拉伯数字举例，我要知道 $19082$ 中哪个子串和 $19$ 相同，你肯定不会作 $1+9=8+2$ 这样的比较就认为 $19=82$ 吧，因为 $19=1\times10+9\neq8\times10+2=82$，而 $19=1\times10+9=1\times10+9=19$！

这启发我们，可以对高位乘上一个数字，比如 $29$，将这一串数看做 $\bold{29}$ 进制，那么比较就轻而易举了。（一般选用 $131$ 或 $13331$）

具体地说，第 $1\sim3$ 项 fix 字符串的 新概念和 为 $5\times29^2+8\times29+23=4460$，而第 $10\sim12$ 项 ixf 字符串的 新概念和 $8\times29^2+23\times29+5=7400$，它们不相同，所以这俩字符串也不相同。

这就是核心思想，可以找一些字符串感受感受 $\sim$

当然，按照前缀和的思想，我们也需要先预处理 新概念前缀和 ，再进行查询操作。

预处理的时候，我们对第 $i$ 项乘上 $29^i$，再求前缀和。比如刚才那个字符串，先乘，得到 $5\times29,~8\times29^2,~23\times29^3,~15\times29^4,~17\times29^5\dots$，即 $145,6728,560947,10609215,348689533$，计算前缀和就是 $145,6873,567820,11177035,359866568$。

如果我要找 $8,23,15$，计算一下它对于的 新概念和 ，是 $8\times29+23\times29^2+15\times29^3=385410$，一一遍历比较：$1\sim3$ 项，$567820-0\ne385410$，不是；$2\sim4$ 项，$(11177035-145)/29=385410$，是的；$3\sim5$ 项，$(359866568-6873)/29^2=427895\ne385410$，不是。（至于为什么要除以 $29^2$，简单来说是预处理的时候多乘了这么多倍，所以还原时要除回来，可以把数字带进去验证一下）

就这样在 $\Theta(n)$ 的时间内完成了遍历。

下面上模板：

定义变量：

1
2
const int H = 29; // 进制数
unsigned long long sum[M], p[M];

预处理：

1
2
3
4
5
6
7
void init() {
	p[0] = 1;
	for (int j = 1; j <= m; j++) {
		p[j] = p[j - 1] * H; // 存储 29 的多少次方
		sum[j] = sum[j - 1] * H + (s[j] - 'a'); // 新概念前缀和
	}
}

查询：

1
2
3
4
5
6
7
8
int get(int i, int j) {
	return sum[j] - sum[i - 1] * p[j - i + 1];
}
int main() {
    if (get(a) == get(l,r)) {
        // a 串和 [l,r] 子串相同
    }
}

好啦，现在你可以尝试完成本文开头那道题目了 $\sim$

AC~code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#define ull unsigned long long
#define Code int main() { int T = 1;
#define Codes int main() { int T; scanf("%d\n", &T); 
#define by while (T--) eachT();
#define HTLDL return 0;
#define HappyNewYear }

const int M = 1e6 + 7;
const int H = 29;
ull sum[M], p[M];
std::string s;

void init(int m) {
	p[0] = 1;
	for (int j = 1; j <= m; j++) {
		p[j] = p[j - 1] * H;
		sum[j] = sum[j - 1] * H + s[j] - 'a';
	}
}

ull get(int i, int j) {
	return sum[j] - sum[i - 1] * p[j - i + 1];
}

void eachT() {
	std::cin >> s;
	int m = s.size();
	s = " " + s;
	init(m);
	for (int len = m - 1; len >= 1; --len) {
		ull h1 = get(1, len), h2 = get(m - len + 1, m);
		if (h1 != h2) continue;
		for (int i = 2; i <= m - len; ++i) {
			h2 = get(i, i + len - 1);
			if (h1 == h2) {
				for (int j = 1; j <= len; ++j)
					std::cout << s[j];
				return;
			}
		}
	}
	std::cout << "I'll write one for you";
}

Code by HTLDL
HappyNewYear

最后附赠一个练习题：

题目描述

就像 小 F 有幸运数字一样，太阳也有喜欢的字符串 $A$。
将 $A$ 的首字母移到末尾，执行任意次，可以得到所有和 $A$ 结构相同的字符串。
小 F 喜欢赞美太阳，同时她还有 $n$ 个字符串 $B_1$，$B_2$，$B_3$……她想知道对于自己的每一个字符串，有多少个子串和 $A$ 结构相同。

输入

第一行为字符串 $A$ 串长 $\leqslant1e6$
第二行为 $n\leqslant1000$
随后 $n$ 行为 $B_1\sim B_n$，单个串长不超过 $1e6$，总串长不超过 $1e7$

输出

输出 $n$ 行，每个串有多少子串与 $A$ 结构相同

样例输入

1
2
3
4
abab
2
abababab
ababcbaba

样例输出

1
2
5
2

作者在一小时前刚初步了解了哈希，并写下了这篇笔记，如有错误恳请各位指出。

应该比较容易理解吧、、、