自动搬运

查看原文

来自洛谷，原作者为

	Eafoo ??? ?? ???? ?????, ? ???? ???????????

搬运于2025-08-24 21:51:25，当前版本为作者最后更新于2022-02-22 11:54:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前置知识：字符串Hash (板子：P3370)

一句话题意：给定 n 个A串和 n 个B串，长度均为 m，求一个最短的区间 $[l,r]$，使得不存在一个A串a和一个B串b，使得 $a[l,r]=b[l,r]$

在这篇题解中，我们使用a来代表A串中的一个串，b来代表B串中的一个串

使用 $a[l, r]$ 来代表 a串中从 l ~ r 位置的子串

最暴力的想法无非于先从小到大枚举最短的子串长度$len$，之后再枚举长度为$len$的所有区间$[l, r] (r = l + len - 1, 1 \le l \le r \le m)$，暴力判断每个A串 $a[l, r]$ 与每个B串 $b[l, r]$ 有没有重复，时间复杂度$O(n ^ 2 * m ^ 3)$，显然会超时

我们考虑判断区间$[l, r]$是否合法的操作进行优化。

具体操作（设当前判断的区间为 $[l, r]$）：

1.在操作进行前预处理出每个A串中 $a[1, x] (1 \le x \le m)$ 的Hash值，假定Hash时的进制数为 $p$ ，模数为 $mod$ ，那就有$Hash[l, r] = (Hash[r] - Hash[l - 1] * p ^ {r - l + 1} + mod) \% mod$

预处理代码：

//strA[i][j]: 第i个A串中第j个字符
//hA[i][j]: 第i个A串中前j个字符构成子串的Hash值

for (int i = 1; i <= n; ++i)
{
	for (int j = 1; j <= m; ++j)
	{
		hA[i][j] = hA[i][j - 1] * p + strA[i][j];
	}
}

2.建立一个从整数映射到bool的map，名叫$vis$，遍历每个A串，将 $vis[Hash(a[l, r])]$ 设为 $true$

3.遍历每个B串，若 $vis[Hash(b[l, r])]$ 为 $true$，则当前区间不合法。若对于所有B串都有 $vis[Hash(b(l, r))] = false$，则当前区间合法。

代码：

//pp[i]为已经预处理好的 p 的 i 次方
map<ull, bool> vis;

bool check(int l, int r)
{
	bool f = 1;
	vis.clear();
	for (int i = 1; i <= n; ++i)
	{
		vis[hA[i][r] - pp[r - l + 1] * hA[i][l - 1]] = 1;
	}
	for (int i = 1; i <= n; ++i)
	{
		if (vis.count(hB[i][r] - pp[r - l + 1] * hB[i][l - 1]))
		{
			f = 0;
			break;
		}
	}
	if (f)
	{
		return true;
	}
	return false;
}

这样我们就可以把判断区间是否合法的操作从 $O(n ^ 2 * m)$ 优化到 $O(n logn * m)$，总时间复杂度 $O(nlogn * m ^ 3)$，仍然会超时。

于是我们考虑二分答案，对从小到大枚举区间长度 $len$ 的操作改为二分枚举，那么总时间复杂度降为 $O(nlogn * m^2logm)$，可以愉快的AC啦~

以下为AC代码：

#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <iostream>
using namespace std;

int read() //快读
{
	int x = 0;
	char c;
	bool f = 0;
	while (!isdigit(c = getchar()))
	{
		if (c == '-')
		{
			f = 1;
		}
	}
	do
	{
		x = (x << 1) + (x << 3) + (c ^ 48);
	} while (isdigit(c = getchar()));
	if (f)
	{
		return -x;
	}
	return x;
}

typedef unsigned long long ull;

const int maxn = 5e2 + 10;
const ull p = 131;

int n, m;

ull pp[maxn]; //p的i次方
ull hA[maxn][maxn], hB[maxn][maxn]; //Hash前缀和
char strA[maxn][maxn], strB[maxn][maxn]; //串

map<ull, bool> vis;

bool check(int len) //判断区间长度为len时合不合法
{
	for (int l = 1, r = l + len - 1; r <= m; ++l, ++r)
	{
		bool f = 1;
		vis.clear();
		for (int i = 1; i <= n; ++i) //枚举所有A串
		{
			vis[hA[i][r] - pp[r - l + 1] * hA[i][l - 1]] = 1;
		}
		for (int i = 1; i <= n; ++i) //枚举所有B串
		{
			if (vis.count(hB[i][r] - pp[r - l + 1] * hB[i][l - 1])) //这种操作尽量用count函数写，直接用下标方式写的话常数大很多
			{
				f = 0;
				break;
			}
		}
		if (f)
		{
			return true;
		}
	}
	return false;
}

int main()
{
	n = read(), m = read();
	pp[0] = 1; //注意
	for (int i = 1; i <= 500; ++i) //预处理p的i次方
	{
		pp[i] = pp[i - 1] * p;
	}
	for (int i = 1; i <= n; ++i)
	{
		scanf("%s", strA[i] + 1);
		for (int j = 1; j <= m; ++j)
		{
        	//预处理前缀Hash
			hA[i][j] = hA[i][j - 1] * p + strA[i][j];
		}
	}
	for (int i = 1; i <= n; ++i)
	{
		scanf("%s", strB[i] + 1);
		for (int j = 1; j <= m; ++j)
		{
			hB[i][j] = hB[i][j - 1] * p + strB[i][j];
		}
	}
	int l = 1, r = m;
	int ans = 0;
	while (l <= r) //二分枚举区间长度
	{
		int mid = (l + r) >> 1;
		if (check(mid))
		{
			ans = mid;
			r = mid - 1;
		}
		else
		{
			l = mid + 1;
		}
	}
	printf("%d\n", ans);
}