题解 P3763 【[TJOI2017]DNA】
Rye_Catcher
2018-04-22 16:25:27
- 题目链接：
https://www.luogu.org/problemnew/show/P3763
- 思路：
首先我们要用到Rabin-Karp哈希，其实就是这个:
- 若$w_{str}$=($a_0$ $p^{n-1}$+$a_1$ $p^{n-2}$+...+$a_{n-1}$ $p^0$)
所以$w_{pre_{i-1}}$ $=($ $a_0$ $p^{i-1}$+$a_1$ $p^{i-2}$+...+$a_{i-1}$ $p^0$)
$w_{pre_{j}}$ $=($ $a_0$ $p^{j}$+$a_1$ $p^{j-1}$+...+$a_{j}$ $p^0$)
所以 $w_{str_{i,j}}$
$=($ $a_i$ $p^{j-i}$+$a_{i+1}$ $p^{j-i-1}$+...+$a_{j}$ $p^0$)
$=$ $w_{pre_{j}}$ $-$ $w_{pre_{i-1}}$ $p^{j-i+1}$
注意了，我这里并没有取模，而是直接直接用unsigned long long 自然溢出，这样更快
然而，一般人都是用二分确定右端点，我自己摸索出了一个骚操作（好像又在哪里听过）----用**倍增**。
因为在这道题中我觉得二分的上下界可能相差比较大，虽然理论上二分平均情况下更好，但在这道题中实际测出来用倍增更快（如果之后有人用二分跑得还比我快就无视我这句话）。
思路就是这样，其他一些细节就见代码吧.
- 代码：
```
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <iostream>
#define ri int
const int maxn=100005;
typedef long long ll;
typedef unsigned long long ull;
char a[maxn],b[maxn];
ull q[maxn],aht[maxn],bht[maxn];
int cnt=0,lena,lenb;
inline void Hash(){
ll x=0;
for(ri i=0;a[i];i++){
x=x*131+a[i]-31;
aht[i]=x;
// cout<<x<<i<<endl;
}x=0;
for(ri i=0;b[i];i++){
x=x*131+b[i]-31;
bht[i]=x;
}x=0;
return ;
}
inline int solve(int x,int y){
int k=0,p=1;
x++,y++;
while(p!=0){
if((aht[x+k+p-1]-aht[x-1-1]*q[k+p+1])==(bht[y+k+p-1]-bht[y-1-1]*q[k+p+1]))k+=p,p*=2;
else p=p/2;//cout<<l<<'*'<<r<<'*'<<mid<<endl;
while(x+k+p>lena||y+k+p>lenb)p=p/2;
}
if(a[x-1]==b[y-1])k++;
return k;
}
inline bool ok(int i){
int la=0,k;
for(ri j=1;j<=3;j++){
k=solve(i,la);
i+=k+1,la+=k+1;
if(la>=lenb){return 1;}//cout<<i<<' '<<la<<endl;
}
k=solve(i,la);
i+=k;la+=k;
// cout<<i<<' '<<la<<endl;
if(la>=lenb) return 1;
return 0;
}
int main()
{
int t;
scanf("%d",&t);
q[0]=1;
for(ri i=1;i<=100001;i++)
q[i]=(ull)q[i-1]*131;
//预处理幂，这个技巧来自https://www.cnblogs.com/sineagle/p/8490655.html
while(t--){
int cnt=0;
scanf("%s",a);
scanf("%s",b);
lena=strlen(a),lenb=strlen(b);
if(lena<lenb){printf("0\n");continue;}
Hash();
for(ri i=0;i<lena-lenb+1;i++){
if(ok(i))cnt++;
}
printf("%d\n",cnt);
memset(aht,0,sizeof(aht));
memset(bht,0,sizeof(bht));
}
return 0;
}
```
- 后记：
luogu上最快的一次跑了240ms,然而还是比不过BZOJ的dalao