题目描述
阿轩在纸上写了两个字符串,分别记为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
题意
给了字符串A,B. 有Q个询问,询问A中后缀和B匹配的长度为x的字符串的个数
算法1
(kmp)
由kmp
中next[i]
数组的定义,可以发现如果字符串B匹配A中的后缀为next[i]
的话, 那么next[i]
包含next[next[i]
。可以一直递归到长度为0。
所以我们可以设f[i]
为字符串B在字符串A中匹配长度至少$i$的个数。
那么长度为x的数量 = $f[x] - f[x + 1]$。
时间复杂度
参考文献
C++ 代码
#include <iostream>
using namespace std;
const int N = 200010;
int n, m, Q;
char a[N], b[N];
int ne[N];
int f[N];
int main(){
cin >> n >> m >> Q;
scanf("%s%s", a + 1, b + 1);
for (int i = 2, j = 0; i <= m; i ++){
while (j && b[i] != b[j + 1]) j = ne[j];
if (b[i] == b[j + 1]) j ++;
ne[i] = j;
}
for (int i = 1, j = 0; i <= n; i ++){
while (j && a[i] != b[j + 1]) j = ne[j];
if (a[i] == b[j + 1]) j ++;
f[j] ++;
}
for (int i = m; i; i --) f[ne[i]] += f[i];
while (Q --){
int x;
cin >> x;
cout << f[x] - f[x + 1] << endl;
}
return 0;
}
算法2 字符串hash。
水平太菜,等待以后补充。