luogu题解 P3763 【[TJOI2017]DNA】

题目链接：
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

Luogu

luogu题解 P3763 【[TJOI2017]DNA】