题解 P3318 【[SDOI2015]双旋转字符串】

· · 题解

题目链接

零.前记

刚打完的时候本机上测是全a的，拿到洛谷和bzoj那里就半分都没有

用各种方法调了几天最后发现.....读入字符炸了 墙在哪里！别来拦我！

一.思路

新的数据范围显示N>=M，我们不难发现字符串t总是短的那一方

因此我们可以把注意力全部集中在串s上，t串的那些直接求个哈希放一边

那我们不妨分n=m和n>m两种情况进行讨论

1.n=m

对于这种情况，我们不难发现就是要求对于每一个s串，有多少个对应t串是它的双旋转字符串

2.n>m

我们发现在s中除去前(n+m)/2的部分之后会多出来一段小东西

这一串小东西与t合在一起之后与s前(n+m)/2的那部分呈双旋转性

那么我们就把这串小东西单独拎出来称为work2，s前(n+m)/2的那部分称为work1

即work1的双旋转字符串=work2+t_i

举个例子

题目中的样例1,在vijosvi中，work1为vijos,work2为vi

于是我们发现vijos的双旋转字符串中有且只有一个字符串vijos=vi+jos

于是我么确定所有的jos都是合法的t串

而t串中只有2个jos,于是对于vijosvi，只有两个合法的t串

我们就可以查找在work1的所有双旋转字符串中，以work2为开头的字符串是哪些，而在那些字符串中，剩下的那部分就是合法的串，再找一下有多少个t串在这些合法串之中。

例子end

二.实现方法及细节

1.求一个串的所有双旋转字符串

不难发现，一个长度为n的字符串的所有双旋转字符串可以这样求：

把字符串倍长，从字符串的头开始到第n个结束，每一个字符及其后面n-1个字符所组成的串就是它的双旋转字符串

举个例子

现有一字符串"vijos",倍长之后就是"vijosvijos"

从头开始到第n个所带领的长度为n的字符串分别是:

"vijos","ijosv","josvi","osvij","svijo"

例子end

2.哈希

i.哈希的思想

我们在n>m的情况中要寻找开头为work2的字符串

因此我们可以在求s的所有双旋转字符串中加一个小操作

在枚举遍历每一个字符的时候先判断一下后面是否是work2

在这里我们直接判断两处的哈希值是否相等

ii.求s串中l~r的部分的哈希值

我们可以类比一下在"816328472375724"这样的一串数中取出第3位至第7位的数

我们发现这完全可以用8163284-8100000=63284来得到

那么类似的我们可以先求出从1到第i个字符的哈希值,用hashqzh_i来表示

那么我们事先求出hashqzh_i之后，对于l~r的哈希，我们可以用一条式子来表示(base为hash的进制)：

ans=hashqzh_r-hashqzh_{l-1}*base^{r-l+1}

综合起来一二部分的代码为：

work2=0;//记得work2初始化(笔者也掉过这个坑 
for(register int j=1;j<=mid;j++){//求hash_qzh 
    hash_qzh[j]=hash_qzh[j-1]*base+s[i*n+j]-'a';
}
for(register int j=1;j<=mid;j++){//求倍长部分的hash_qzh 
    hash_qzh[j+mid]=hash_qzh[j+mid-1]*base+s[i*n+j]-'a';
}
for(register int j=mid+1;j<=n;j++)//求work2的哈希值 
    work2=work2*base+s[i*n+j]-'a';

求前缀哈希值的部分为:

inline unsigned long long search(int l,int r,unsigned long long flag){//flag=base^(r-l+1) 
    return hash_qzh[r]-hash_qzh[l-1]*flag;
}

3.sort去重

(此为大坑，需多加注意)

我们已经知道怎么求合法的t串了，可是我们还要考虑到重复的问题

举个例子

有一个s串为viovi,t串为o

于是work1为viovioviovio而work2为vi

但是我们在匹配的时候会在第一个和第四个位置算了两次o

可我们知道t中只有一个o

于是就翻车了

例子end

因此每次找到就统计一次的方法是错误的

我们需要拿一个队列把可行的t存起来去重

即把可行的t的哈希存在队列里sort一下

4.平衡树 假

我们只剩下一个问题，就是如何查找t串的数量

我们可以运用强大的stl

实在喜欢可以手敲平衡树，博主这里用的是multiset

我们把t串的哈希求出来之后放在一个multiset里

每次就直接把哈希值为某个数的t串搞出来

5.智能存储

我们在存s串的时候可能会有疑惑

最糟糕的情况不分别是n=4e6和totals=4e6吗，两个乘起来怎么存

但是我们发现两种情况的空间都是有很大的浪费的

再加上n\times totals<=4e6

于是我们可以把totals个串合在一起成为S串

对于第i个s串，它所在的位置为S[(i-1)\times n+1......i\times n]

三.代码

#include<cstdio>
#include<set>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=4e6+5;
const int base=29;
int ts,tt,n,m,mid;//mid=(n+m)/2,ts和tt:totals和totalt
char ch,s[maxn];//s串 
multiset <unsigned long long> hashh;//存t串的multiset 
unsigned long long hash_qzh[maxn],ans,work2;//前缀哈希 
unsigned long long flag1=1,flag2=1;//flag1=base^n-mid,flag2=base^m
unsigned long long  dl[maxn];//去重用队列 
inline void init(){//读入 
    scanf("%d%d%d%d",&ts,&tt,&n,&m);
    mid=(n+m)>>1;
    for(register int i=0;i<ts;i++){//读入s串，注意智能储存 
        for(register int j=i*n+1;j<=(i+1)*n;j++){
            s[j]=getchar();
            while(s[j]<'a' || s[j]>'z')s[j]=getchar();
        }
    }
    for(register int i=1;i<=tt;i++){
        unsigned long long hash_t=0;
        for(register int j=1;j<=m;j++){
            char ch=getchar();
            while(ch<'a' || ch>'z')ch=getchar();
            hash_t=hash_t*base+(ch-'a');
        }
        hashh.insert(hash_t);//存multiset 
    }
    return ;
}
inline unsigned long long search(int l,int r,unsigned long long flag){//flag=base^(r-l+1) 
    return hash_qzh[r]-hash_qzh[l-1]*flag;
}
inline void workk(){//对应n>m的情况 
    dl[0]=0;
    for(register int i=1;i<=mid;i++){
        int j=i+n-mid-1;//i为头,j为末尾
        if(search(i,j,flag1)==work2)//如果那一段等于work2 
            dl[++dl[0]]=search(j+1,j+m,flag2);//把所对应的t值放入队列 
    }
    sort(dl+1,dl+dl[0]+1);//排个序去重 
    for(register int i=1;i<dl[0];i++){//在multiset中找一下 
        if(dl[i+1]!=dl[i]) ans+=hashh.count(dl[i]);
    }
    ans+=hashh.count(dl[dl[0]]);
    return ;
}
inline void workk2(){//对于n=m的情况，与上面类比 
    dl[0]=0;
    for(register int i=1;i<=mid;i++){
        dl[++dl[0]]=search(i,i+m-1,flag2);
    }
    sort(dl+1,dl+dl[0]+1);
    for(register int i=1;i<dl[0];i++){
        if(dl[i+1]!=dl[i]) ans+=hashh.count(dl[i]);
    }
    ans+=hashh.count(dl[dl[0]]);
    return ;
}
int main(){
    init();
    for(register int i=1;i<=n-mid;i++)
        flag1*=base;
    for(register int i=1;i<=m;i++)
        flag2*=base;
    for(register int i=0;i<ts;i++){
        work2=0;//记得work2初始化(笔者也掉过这个坑 
        for(register int j=1;j<=mid;j++){//求hash_qzh 
            hash_qzh[j]=hash_qzh[j-1]*base+s[i*n+j]-'a';
        }
        for(register int j=1;j<=mid;j++){//求倍长部分的hash_qzh 
            hash_qzh[j+mid]=hash_qzh[j+mid-1]*base+s[i*n+j]-'a';
        }
        for(register int j=mid+1;j<=n;j++)//求work2的哈希值 
            work2=work2*base+s[i*n+j]-'a';
        if(n>m) workk();//两种情况讨论 
        else workk2();
    }
    printf("%llu\n",ans);
    return 0;
}

四.总结

1.千万不能像我一样卡在读入这种东西上

2.用hash来帮忙解决匹配的问题(毕竟本来就要用，没必要再打一个kmp了)

3.运用stl来优化代码(时间除外)

温馨提示

本题解偏向于给萌新(虽然似乎并无萌新会来做黑题)，故写的非常详细，看不顺眼的大佬们不要喷qwq

博主语文超级烂，表述地方有问题多多见谅qwq

博主代码很水，luogu上要开O2才可以过，勿diss qwq

Finally，谢谢大家

更好的阅读体验