题目描述
阿轩在纸上写了两个字符串,分别记为 A 和 B。
利用在数据结构与算法课上学到的知识,他很容易地求出了“字符串 A 从任意位置开始的后缀子串”与“字符串 B”匹配的长度。
不过阿轩是一个勤学好问的同学,他向你提出了 Q 个问题:
在每个问题中,他给定你一个整数 x,请你告诉他有多少个位置,满足“字符串 A 从该位置开始的后缀子串”与 B 匹配的长度恰好为 x。
例如:A=aabcde,B=ab,则 A 有 aabcde、abcde、bcde、cde、de、e 这 6 个后缀子串,它们与 B=ab 的匹配长度分别是 1、2、0、0、0、0。
因此 A 有 4 个位置与 B 的匹配长度恰好为 0,有 1 个位置的匹配长度恰好为 1,有 1 个位置的匹配长度恰好为 2。
样例
输入样例:
6 2 5
aabcde
ab
0
1
2
3
4
输出样例:
4
1
1
0
0
算法
(字符串hash+二分) $O(nlogn)$
算法思路:预处理所有a的后缀与b的匹配长度
预处理思路:
二分求长度 二分左端点0 二分右端点b的长度
之后对于每一个a的后缀(在这里我是通过枚举a的开头)求匹配长度之后存起来
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;
const int N=200010,base=131;
int cnt[N];
ull p[N],ha[N],hb[N];
char a[N],b[N];
int n,m,k;
ull get(ull h[],int l,int r)
{
return h[r]-h[l-1]*p[r-l+1];
}
bool check(int sta,int len)
{
return get(ha,sta,sta+len-1)==get(hb,1,len);
}
int main()
{
cin>>n>>m>>k;
scanf("%s",a+1);
scanf("%s",b+1);
p[0]=1;
ha[0]=0;
for(int i=1;i<=n;i++)
{
p[i]=p[i-1]*base;
ha[i]=ha[i-1]*base+a[i]-'a'+1;
}
for(int i=1;i<=m;i++)
hb[i]=hb[i-1]*base+b[i]-'a'+1;
for(int i=1;i<=n;i++)//枚举a的开头
{
int l=0,r=m;//枚举长度
while(l<r)
{
int mid=l+r+1>>1;
if(check(i,mid)) l=mid;
else r=mid-1;
}
cnt[r]++;
}
while(k--)
{
int q;
scanf("%d",&q);
cout<<cnt[q]<<endl;
}
}
bool check(int sta,int len)
{
return get(ha,sta,sta+len-1)==get(hb,1,len);
}
check这块怎么写,搞不懂从哪里取到哪里..
自己可以带几个数字进去模拟一下