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