自动搬运

查看原文

来自洛谷，原作者为

	Liquefyx 哦

搬运于2025-08-24 22:34:27，当前版本为作者最后更新于2023-06-24 18:13:40，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

先说个题外话，这道题哈希用 $29$，会 WA 几个点！？？？（2023.6.24）

upd：原因是写代码的时候没发现字符串访问了未赋值的地方导致哈希出了问题……有点内个了 o(╥﹏╥)o，哈希用 $29$ 也是可以的（2023.10.17）

题意

已知 $N$ 个长度不超过 $30$ 的字符串 $S_i$，有 $Q$ 次询问，每次询问给出一个长度依旧不超过 $30$ 的字符串 $T_i$，求出 $T_i$ 在 $S_i$ 中第一次出现的位置 $w_i$（没有则为 $N$）加上 $i=1\sim w$ 的 $S_i$ 与 $T_i$ 的最长公共前缀的长度之和。

题目分析

首先一看内存限制，好家伙，32 MB，字典树建不下，这可怎么办？但我们可以发现，我们可以将询问离线下来，分开求 $w_i$ 和最长公共前缀的长度之和。

求 $w_i$ 是比较简单的，直接 hash+unordered_map 就行了，接着我们考虑求最长公共前缀的长度之和，由于这道题的字符串长度并不是非常大，我们可以将 $S_i$ 和 $T_i$ 的每个前缀单独拎出来然后求哈希值，再用 unordered_map 统计与 $T_i$ 的前缀的哈希值、长度均相同的 $S_i$ 的前缀的个数之和，而这即为最长公共前缀的长度之和，具体细节可以康康代码。

时间复杂度是优秀的 $O(N\times |S|)$，空间复杂度也是 $O(N\times |S|)$。

Code

#include <bits/stdc++.h>
#define uLL unsigned long long
using namespace std;
const int N = 3e4+5;
const uLL base = 31;
int n, q, ans[N];
uLL az[N], bb[N];
unordered_map <uLL, int> vis;
char s[N][35], t[N][35];
vector <int> to[N];

template <typename T> void read(T& x) {
	x = 0; int f = 0; char c = getchar();
	while(c < '0' || c > '9') f |= (c == '-'), c=getchar();
	while(c >= '0' && c <= '9') x=(x<<1)+(x<<3)+(c^48), c=getchar();
	x=(f ? -x : x);
}
int lne; char put[105];
template <typename T> void write(T x, char ch) {
	lne = 0; if(x < 0) putchar('-'), x=-x;
	do { put[++lne]=x%10, x/=10; } while(x);
	while(lne) putchar(put[lne--]^48);
	putchar(ch);
}

signed main() {
	read(n);
	for(int i = 1; i <= n; ++i) {
		scanf("%s", s[i]+1);
		int ln = strlen(s[i]+1);
		for(int len = 1; len <= ln; ++len)
			az[i]=az[i]*base+s[i][len]-'a'+1;
		if(vis.find(az[i]) == vis.end())
			vis[az[i]]=i;//先统计第一个哈希值为这个的S_i的位置 
	}
	read(q);
	for(int i = 1; i <= q; ++i) {
		scanf("%s", t[i]+1);
		int ln = strlen(t[i]+1);
		for(int o = 1; o <= ln; ++o)
			bb[i]=bb[i]*base+t[i][o]-'a'+1;
		if(vis.find(bb[i]) == vis.end())//找w_i,找不到就是n 
			to[n+1].push_back(i), ans[i]+=n;
		else
			to[vis[bb[i]]].push_back(i), ans[i]+=vis[bb[i]];
	}
	for(int i = 1; i <= n; ++i) 
		az[i]=0;
	for(int i = 1; i <= q; ++i) 
		bb[i]=0;
	for(int len = 1; len <= 30; ++len) {
		vis.clear();
		for(int i = 1; i <= q; ++i) 
			if(strlen(t[i]+1) >= len) //upd:!!!就是这个地方!!!一定要判 
				bb[i]=bb[i]*base+t[i][len]-'a'+1;//更新哈希值 
		for(int i = 1; i <= n; ++i) {
			if(strlen(s[i]+1) < len) continue;//长度小的不算 
			az[i]=az[i]*base+s[i][len]-'a'+1;
			++vis[az[i]];//统计个数 
			for(int j : to[i]) //找到w_i等于i的T_i贡献答案 
				if(vis.find(bb[j]) != vis.end())
					ans[j]+=vis[bb[j]];//贡献答案 
		}
		for(int j : to[n+1])//特殊处理找不到w_i的T_i 
			if(vis.find(bb[j]) != vis.end())
				ans[j]+=vis[bb[j]];
	}
	for(int i = 1; i <= q; ++i) 
		write(ans[i], '\n');
	return 0;
}