题解 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_{str_{i,j}} $=$ $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