列表

详情

NC19822. 我不爱她

描述

终于活成了自己讨厌的样子。

天空仍灿烂，它爱着大海。

你喜欢大海，我爱过你。

世界上充满了巧合。我们把每句话当成一个字符串，我们定义a对b的巧合值为a的最长后缀的长度并且它是恰好是b的前缀，这里的后缀或者前缀包括字符串的本身。
比如字符串“天空仍灿烂她喜欢大海”对“她喜欢大海我不爱她了我爱的只是与她初见时蔚蓝的天空”的巧合值为5，而字符串“她喜欢大海我不爱她了我爱的只是与她初见时蔚蓝的天空”对“天空仍灿烂她喜欢大海”的巧合值为2。
现在给出n个字符串由"ab"构成的字符串s1,s2,...,sn，求出对于所有1≤ i,j≤ n，si对sj的巧合值的和。

输入描述

第一行一个整数T(T≤ 1000)，表示数据组数。
每组数据第一行一个正整数n(1≤ n≤ 105)。接下来n行每行一个字符串si，保证字符串由"ab"构成。
保证单组数据有，保证所有数据有。

输出描述

对于每组数据，输出一个整数，表示答案。

示例1

输入: 

1
2
abb
bab

输出: 

9

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(clang++ 11.0.1) 解法, 执行用时: 815ms, 内存消耗: 38460K, 提交时间: 2022-08-19 20:57:47 

#include<bits/stdc++.h>
using namespace std;
#define P 131
unsigned long long T,n,ans,len,hs,p,ne[1500005];
unordered_map<unsigned long long,int> mp;
string s[100005];
int main()
{
	cin>>T;
	while(T--)
	{
		cin>>n;ans=0;
		mp.clear();
		for(int i=1;i<=n;i++) 
		{
			cin>>s[i];
			len=s[i].length();hs=0;p=1;
			for(int j=len-1;j>=0;j--)
			{
				hs=hs+(s[i][j]-'a'+1)*p;
				p=p*P;mp[hs]++;
			}
		}
		for(int i=1;i<=n;i++)
		{
			len=s[i].length();ne[0]=-1;//从零开始的kmp改写 
			for(int j=1,k=-1;j<len;j++)
			{
				while(k>=0&&s[i][j]!=s[i][k+1]) k=ne[k];
				if(s[i][j]==s[i][k+1]) k++;
				ne[j]=k;
			}hs=0;
			for(int j=0;j<len;j++)
			{
				hs=hs*P+s[i][j]-'a'+1;
				ans+=mp[hs]*(j-ne[j]);//之前ne[j]这份长度已计入 则减去 不重复计入 
			}
		}cout<<ans<<endl;
	}
}

上一题

© 2024 nowcoder.com