码农场
出题：众所周知，程序竞赛测试数据越变态越好玩。已知3个字符串会使选手的程序出错，出题者想构造一个超级变态数据同时包含这3个字符串。求该母串最小长度。
4.7华丽地处理字符串
字符串匹配
利用滚动哈希法可以快速预处理出字符串的哈希值以及基数的n次方表。
如果这些字符串有包含关系，则只取母串x，与剩下的第3个串y进行讨论。如果x和y有包含关系，则取母串作为答案。否则答案为x与y的两种拼接xy和yx中的较小者。
如果没有任何包含关系，那么遍历三个字符串的所有拼接方式，取其最小者作为最终答案。
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
using ull = unsigned long long;
const int MAX_LENGTH = 100000 + 8;
const ull B = 100000007ULL; // 哈希的基数
char s[3][MAX_LENGTH];
ull H[3][MAX_LENGTH], // H[i][j] := s_i的长度为j的前缀的哈希值
B_to[MAX_LENGTH] = {1ULL}; // B_to[i] := B^i
int id[3] = {0, 1, 2}, len[3];
void init_hash()
{
for (int i = 0; i < 3; ++i)
{// 初始化前缀的哈希值
for (int j = 1; j < len[i] + 1; ++j)
{
H[i][j] = H[i][j - 1] * B + s[i][j];
}
}
int n = max(max(len[0], len[1]), len[2]);
for (int i = 1; i < n + 1; ++i)
{
B_to[i] = B_to[i - 1] * B;
}
}
// s[b...b+l)的哈希值
inline ull hash_of(ull *h, int b, int l)
{
return h[b + l - 1] - h[b - 1] * B_to[l];
}
// b是否在a中出现(a是否包含b）
bool contain(int a, int b)
{
if (len[a] < len[b])
return false;
ull bh = H[b][len[b]]; // b全长对应的哈希值
for (int i = 1; i + len[b] <= len[a]; ++i) // 对a不断右移一位，更新哈希值并判断
if (hash_of(H[a], i, len[b]) == bh) // a从位置i开始长度为len[b]的子串等于b
return true;
return false;
}
// a的后缀和b的前缀相等的最大长度
int overlap(int a, int b)
{
int ans = 0;
for (int i = 1; i <= min(len[a], len[b]); ++i)
{// a的长度为i的后缀与b的长度为i的前缀的哈希值是否相等
if (hash_of(H[a], len[a] - i + 1, i) == hash_of(H[b], 1, i))
ans = i;
}
return ans;
}
int solve()
{
int ans = MAX_LENGTH * 3;
for (int i = 0; i < 2; ++i)
{
for (int j = i + 1; j < 3; ++j)
{
if (contain(i, j) || contain(j, i))
{
int x = len[i] > len[j] ? i : j, y = 3 - i - j; // x为母串，y为除母子串外的第三个串
if (contain(x, y) || contain(y, x)) // x和y有包含关系
return max(len[x], len[y]);
return len[x] + len[y] - max(overlap(x, y), overlap(y, x)); // x和y拼接起来
}
}
}
do // 无包含关系，只好遍历所有拼接方式
ans = min(ans, len[0] + len[1] + len[2] - overlap(id[0], id[1]) - overlap(id[1], id[2]));
while (next_permutation(id, id + 3));
return ans;
}
int main()
{
for (int i = 0; i < 3; ++i)
{
gets(s[i] + 1), len[i] = strlen(s[i] + 1); // 首部预留一个\0，方便递推hash
}
init_hash();
printf("%d\n", solve());
return 0;
}
Reference
这份模板比书上的要好：http://endless.logdown.com/posts/2014/04/15/codeforces-beta-round-25-25e-test-hash
