北化排位赛（三）K 下笔成章［简中］

返回全部题目

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

样例输入

fixprefixixffix

样例输出

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)$ 的时间内完成了遍历。

---

下面上模板：

定义变量：

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

预处理：

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'); // 新概念前缀和
	}
}

查询：

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

#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$ 结构相同

样例输入

abab
2
abababab
ababcbaba

样例输出

5
2

---

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

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