自动搬运

查看原文

来自洛谷，原作者为

	lc_lca i ak ioi

搬运于2025-08-24 22:00:00，当前版本为作者最后更新于2020-01-29 23:02:14，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

其实这道题远不用写进制版的hash

首先开个map<string,int>mp记录每个字符串的所有子串在几个串中出现。

例如说有个串abc就mp[a]++,mp[ab]++,mp[abc]++,mp[b]++,mp[bc]++,mp[c]++;

但是这就出问题了

假如一个串是aa那么mp[a]被加了两次，而一个子串只能对于当前串的贡献为1

所以用一个map<string,bool>tmp记录当前每个子串是否被加过，被加过就不再加了。

当然tmp在每一个串都要清零。

预计复杂度 20000 * 55 * log20000

#include<bits/stdc++.h>
using namespace std;
map<string,int>mp;
map<string,bool>tmp;
string s[20010];
int main()
{
	int n;
	scanf("%d",&n);
	mp.clear();
	for(int i=1;i<=n;i++)
	{
		cin>>s[i];
		tmp.clear();
		int len=s[i].length();
		for(int k=1;k<=len;k++)
		{
			for(int j=k;j<=len;j++)
			{
				string t=s[i].substr(k-1,j-k+1);//截取子串，开头是k-1，长度是j-k+1
				if(tmp[t]==true)continue;
				tmp[t]=true;
				mp[t]++;
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		ans+=mp[s[i]]-1;//统计
	}
	cout<<ans<<endl;
	return 0;
}