武辰延的字符串

题目链接https://ac.nowcoder.com/acm/contest/9984/B

解题思路

字符串哈希+二分
首先，当s[x]!=t[x]时，如果i>=x，此时不存在
当s[x]==t[x]时，需要寻找s的一个最长的前缀使得 ，这就需要用字符串哈希快速判断字符串是否相等，二分缩小答案区间

时间复杂度O(nlog(n))

AC代码

#include <bits/stdc++.h>

#define endl '\n'
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int N=1e5+10;
const int P=13331; 
char a[N];
char b[N];
ull h1[N],h2[N],p[N];

ull gethash1(int l,int r)
{
    if(l>r) return 0;
    return h1[r]-h1[l-1]*p[r-l+1];
}

ull gethash2(int l,int r)
{
    if(l>r) return 0;
    return h2[r]-h2[l-1]*p[r-l+1];
}

bool check(int k,int x)
{
    return gethash1(1,x)==gethash2(k+1,k+x);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>a+1>>b+1;
    int m=strlen(a+1);
    int n=strlen(b+1);
    int l=max(m,n);
    p[0]=1;
    for(int i=1;i<=l;i++)
    {
        if(i<=m) h1[i]=h1[i-1]*P+a[i];
        if(i<=n) h2[i]=h2[i-1]*P+b[i];
        p[i]=p[i-1]*P;
    }
    ll ans=0;
    for(int i=1;i<=m&&i<n;i++)
    {
        if(a[i]!=b[i]) break;
        int l=0,r=n-i;
        while(l<r)
        {
            int mid=(l+r+1)>>1;
            if(check(i,mid)) l=mid;
            else r=mid-1;
        }
        ans+=l;
    }
    cout<<ans<<endl;

    return 0;
}