可能是有$O(n+m+q)$的做法,但我只会$O(nlogn)$的【我太菜了】
化简一下题意,就是对于串$A$的每个后缀,求与串$B$的最大相同前缀(也就是最长公共前缀)
最长公共前缀?那不就是《后缀数组》那题的求法吗?
先预处理$A,B$的前缀Hash值,然后二分找最长公共前缀即可。
时间复杂度$O(nlogn)$
(按理说字符串Hash要三Hash才稳,但为了代码简洁就base131%ull了(其实是懒))
//Wan Hong 2.2
//home
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
typedef long long ll;
typedef std::pair<ll,ll> pll;
typedef std::string str;
#define INF (1ll<<58)
ll read()
{
ll f=1,x=0;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
ll max(ll a,ll b)
{
return a>b?a:b;
}
ll min(ll a,ll b)
{
return a<b?a:b;
}
bool umax(ll& a,ll b)
{
if(b>a)return a=b,1;
return 0;
}
bool umin(ll& a,ll b)
{
if(b<a)return a=b,1;
return 0;
}
/**********/
#define MAXN 200011
typedef unsigned long long ull;
char a[MAXN],b[MAXN];
ull fa[MAXN],fb[MAXN],pw[MAXN];
ll n,m,q,c[MAXN];
ll get(ull* f,ull l,ull r)//在前缀Hash数组中求[l,r]的Hash值,O(1)
{
return f[r]-f[l-1]*pw[r-l+1];
}
int main()
{
n=read(),m=read(),q=read();
scanf("%s%s",a+1,b+1);
pw[0]=1;
for(ll i=1;i<=n;++i)//预处理前缀Hash值
{
pw[i]=pw[i-1]*131;
fa[i]=fa[i-1]*131+a[i]-'0';
}
for(ll i=1;i<=m;++i)fb[i]=fb[i-1]*131+b[i]-'0';
for(ll i=1;i<=n;++i)
{
ull l=0,r=min(n-i+1,m),mid;
while(l<r)//二分最长公共前缀
{
mid=(l+r+1)>>1;
if(get(fa,i,i+mid-1)==get(fb,1,mid))l=mid;
else r=mid-1;
}
++c[l];
}
for(ll i=1;i<=q;++i)
{
ll x=read();
printf("%lld\n",c[x]);
}
return 0;
}
啥是
三Hash
啊?就选三个模数做hash,都相同才判定为相等
哦哦哦懂了,谢谢大佬
你好,我认为你的做法的时间复杂度不是O(N)的;你对每个后缀的最大匹配长度进行了二分答案,我认为这个
算法的渐进时间复杂度为(NlogN).
多谢指正(我上面写的$O(nlogn)$下面就变成$O(n)$真是。。)
fixed