[bzoj4084][Sdoi2015]双旋转字符串

双旋转字符串 bzoj-4084 Sdoi-2015

题目大意：给定两个字符串集合 S 和 T 。其中 S 中的所有字符串长度都恰好为 N ，而 T 中所有字符串长度都恰好为 M 。且 N+M 恰好为偶数。如果记 S 中字符串全体为 S1，S2，...，STotalS ,而 T 中字符串全体为 T1，T2，...，TTotalT 。现在希望知道有多少对 <i,j> ，满足将 Si 和 Tj 拼接后得到的字符串 Si+Tj 满足双旋转性。一个长度为偶数字符串 W 可以表示成两段长度相同的字符串的拼接，即W=U+V。如果 V 可以通过 U 旋转得到，则称 W 是满足双旋转性的。比如说字符串 U=“vijos”可以通过旋转得到“ijosv”，“josvi”，“osvij” 或“svijo”。那么“vijosjosvi”就是满足双旋转性的字符串。

想法：我们将小的集合所有串hash然后存起来，这一步是容易的。对于大串我们将他所有旋转后的前(len1-mid)也存起来，这里只需要将每一个大串在尾部copy一遍，然后hash前缀和即可。mid的意思就是大、小串的长度平均值。然后暴力枚举匹配即可。

最后，附上丑陋的代码... ...

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <map>

#define N 8000010

using namespace std;

typedef unsigned long long ull;

ull h[N],g[N],f[N];

map<ull,int>MP;

char s[N];

int ans;

const int base=233;

int n,m,S,T,k,mid;

void find()

{

	ull x=0;

	int cnt=0;

	for(int i=mid+1;i<=n;i++) x=x*base+s[i];

	for(int i=1;i<=mid;i++) s[i+mid]=s[i];

	for(int i=1;i<=mid*2;i++) f[i]=f[i-1]*base+s[i];

	for(int i=1;i<=mid;i++)

	{

		ull y=f[i+k-1]-f[i-1]*h[k];

		if(y!=x) continue;

		g[++cnt]=f[i+mid-1]-f[i+k-1]*h[mid-k];

	}

	sort(g+1,g+cnt+1);

	for(int i=1;i<=cnt;i++) if(g[i]!=g[i-1]) MP[g[i]]++;

}

int main()

{

	scanf("%d%d%d%d",&S,&T,&n,&m);

	h[0]=1;

	for(int i=1;i<=n+m;i++) h[i]=h[i-1]*base;

	mid=(n+m)>>1;

	k=n-mid;

	for(int i=1;i<=S;i++)

	{

		scanf("%s",s+1);

		find();

	}

	for(int i=1;i<=T;i++)

	{

		scanf("%s",s+1);

		ull x=0;

		for(int j=1;j<=m;j++) x=x*base+s[j];

		ans+=MP[x];

	}

	printf("%d",ans);

}

小结：map真好用...hash真强... ...

巴特西

[bzoj4084][Sdoi2015]双旋转字符串_hash

最新文章

热门文章