免费做头像网站,手机端网站开发价格,搭建一个平台需要什么,外贸网站建设基础题目大意
给出nnn个长度为lll且互不相同的串#xff0c;若两个串只有一个字符不相同那么这两个串相似。
求有多少对相似的串。 解题思路
我们可以枚举不相似的位#xff0c;然后我们考虑字符串hashhashhash
然后我们可以将删掉了一位的字符串拆分为由[1..k−1][1..k-1][1…题目大意
给出nnn个长度为lll且互不相同的串若两个串只有一个字符不相同那么这两个串相似。
求有多少对相似的串。 解题思路
我们可以枚举不相似的位然后我们考虑字符串hashhashhash
然后我们可以将删掉了一位的字符串拆分为由[1..k−1][1..k-1][1..k−1]和[k1..l][k1..l][k1..l]组成的字符串。
我们先正着求一遍hashhashhash定为hashihash_ihashi然后倒着求一遍hashhashhash定为dhashidhash_idhashi。
然后删除第kkk位之后的hashhashhash值为hashkdhashk∗pkhash_kdhash_k*p^khashkdhashk∗pk
然后排序统计即可。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ull unsigned long long
using namespace std;
const int N30100,L210;
const ull p13331;
ull hash[N],hash1[N][L],hash2[N][L],pow;
int n,l,ans;
char s[N][L];
void work(int k)
{for(int i1;in;i)hash[i]hash1[i][k-1]hash2[i][k1]*pow;sort(hash1,hash1n);hash[n1]23333333;int num0;for(int i1;in;i){num;if(hash[i]!hash[i1])ansnum*(num-1)/2,num0;}
}
int main()
{scanf(%d%d%d,n,l,pow);for(int i1;in;i){scanf(%s,s[i]1);for(int j1;jl;j)hash1[i][j]hash1[i][j-1]*ps[i][j];for(int jl;j1;j--)hash2[i][j]hash2[i][j1]*ps[i][j];}pow1;for(int i1;il;i)pow*p,work(i);printf(%d,ans);
}
