SPOJ SP34020 ADAPET - Ada and Pet

链接
难度：\(\texttt{13/19}\)

\(T\) 组数据。

你需要构造一个字符串满足其中包含 \(k\) 个给定的字符串 \(s\)，输出该字符串的最短长度。

数据范围：\(k\le 10^6,\sum |s| \le 5 \times 10^5\)

KMP 熟练度考验？

先不考虑头尾相交的情况，若就是 \(k\) 个 \(s\) 拼在一起，答案为 \(k \times |s|\)。

接下来考虑首尾相交的情况，发现这种情况需满足前缀和后缀在给定长度下是相同的，便能由此想到 KMP 时求的 \(nxt\) 数组，因为仅会有 \(k-1\) 个相交部分，所以该部分减掉的贡献为 \((k-1)\times nxt_{|s|}\)。

// Problem: Ada and Pet
// Contest: SPOJ - Classical
// URL: https://www.spoj.com/problems/ADAPET/
// Memory Limit: 1536 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

# include <bits/stdc++.h>
using namespace std;
const int N = 500000;
int KMP [N + 10];
char s [N + 10];
int main () {
	ios :: sync_with_stdio (false);
	cin .tie (0);
	cout .tie (0);
	int t;
	cin >> t;
	while (t --) {
		cin >> (s + 1);
		int n = strlen (s + 1), k;
		cin >> k;
		for (int i = 2, j = 0; i <= n; ++ i) {
			while ((s [j + 1] ^ s [i]) && j) {
				j = KMP [j];
			}
			if (! (s [j + 1] ^ s [i])) {
				++ j;
			}
			KMP [i] = j;
		}// KMP 模板
		cout << 1LL * k * n - 1LL * (k - 1) * KMP [n] << '\n';// 注意这里 k * n 会爆 int 需开 LL
	}
	return 0;
}