字符串哈希+二分

抽象一下题目,其实题目就是要让你求在a串中有多少个位置i,
使得a[i..n]和b[1..m]的最长公共前缀的长度恰好为x(注意是恰好,不能多,也不能少).

听说正解是扩展KMP....
但我不会呀!!!

于是上字符串哈希吧…
先预处理出k的幂次,a串的哈希值,b串的哈希值.
然后我们就要考虑如何求出a[i..n]和b[1..m]的最长公共前缀的长度.

枚举长度,计算哈希值???
明显会超时.

观察一下数据范围,n,m,q<=200000,感觉是个$nlogn$的算法.
这不就是二分吗!!!!
直接二分最长匹配长度,计算哈希值即可.

时间复杂度 $O(nlogn)$

C++ 代码

//相信奇迹的人,本身就和奇迹一样了不起.
#include<bits/stdc++.h>
#define N 200010
#define ll long long
using namespace std;
const ll k=131;
int n,m,q;
ll Hash_a[N],Hash_b[N],power_k[N];
ll cnt[N];
char a[N],b[N];
inline void init()//预处理k的幂次,a串的哈希值,b串的哈希值
{
    power_k[0]=1;
    for(int i=1;i<=max(n,m);i++) 
        power_k[i]=(power_k[i-1]*k);
    for(int i=1;i<=n;i++) 
        Hash_a[i]=(Hash_a[i-1]*k+a[i]);
    for(int i=1;i<=m;i++) 
        Hash_b[i]=(Hash_b[i-1]*k+b[i]);
}
inline ll get_Hash_a(int x,int y){//求a的子串a[x..y]的哈希值
    return Hash_a[y]-Hash_a[x-1]*power_k[y-x+1];
}
inline ll get_Hash_b(int x,int y){//求b的子串b[x..y]的哈希值
    return Hash_b[y]-Hash_b[x-1]*power_k[y-x+1];
}
int main()
{

    scanf("%d %d %d",&n,&m,&q);
    scanf("%s",a+1);
    scanf("%s",b+1);
    init();
    for(int i=1;i<=n;i++){
        if(a[i]!=b[1]){//如果第一个字符都不匹配,则最大匹配长度为0
            cnt[0]++;
            continue;
        }
        int l=1,r=min(m,n+1-i);
        while(l<r){//寻找最大匹配长度
            int mid=(l+r+1)>>1;
            if(get_Hash_b(1,mid)==get_Hash_a(i,i+mid-1))//如果当前可以匹配,向上缩短下界
                l=mid;
            else //否则向下缩短上界
                r=mid-1;
        }
        cnt[r]++;//当前长度的匹配位置+1
    }
     while(q--){
        int x;
        scanf("%d",&x);
        printf("%lld\n",cnt[x]);
    }
    return 0;
}