博客

给定一个长度为 nn 的字符串 S=s1s2…snS=s1s2…sn 以及一个长度为 mm 的字符串 T=t1t2…tmT=t1t2…tm。

两个字符串都由小写字母构成。

用 s[l,r]s[l,r] 来表示字符串 SS 的子串 slsl+1…srslsl+1…sr。

有 qq 个询问，每个询问给出两个整数 li,rili,ri（1≤li≤ri≤n1≤li≤ri≤n），请你计算字符串 TT 在 s[li,ri]s[li,ri] 中作为

子串

出现了多少次。

例如，字符串

abacabadabacaba

中共包含 44 个子串

ba

，所以

ba

在

abacabadabacaba

中作为子串出现了 44 次。

输入格式

第一行包含三个整数 n,m,qn,m,q。

第二行包含一个长度为 nn 的由小写字母构成的字符串 SS。

第三行包含一个长度为 mm 的由小写字母构成的字符串 TT。

接下来 qq 行，每行包含两个整数 li,rili,ri。

输出格式

每个询问输出一行答案，一个整数，表示出现次数。

数据范围

前三个测试点满足 1≤n,m,q≤201≤n,m,q≤20。

所有测试点满足 1≤n,m≤10001≤n,m≤1000，1≤q≤1051≤q≤105，1≤li≤ri≤n1≤li≤ri≤n。

输入样例1：

15 2 3
abacabadabacaba
ba
1 15
3 4
2 14

输出样例1：

4
0
3

输入样例2：

3 5 2
aaa
baaab
1 3
1 1

输出样例2：

0
0

代码如下：

#include<iostream>
#include<cstring>
using namespace std;

int n, m, q, ans = 0;
char a[1005], b[1005];
int ne[1005];
int res[1005][1005];

void getNext(int n) {
    int i = 1, j = 0;
    ne[i] = j;
    while(i <= n) {
        if(j == 0 || b[i] == b[j])
            ne[++i] = ++j;
        else j = ne[j];
    }
    
}

void search(int n, int m) {
    int i = 1, j = 1;
    while(i <= n) {
        if(j == m && a[i] == b[j]) {
            res[i - m + 1][i] = 1;
            j = ne[j];
        }
        if(a[i] == b[j]) {
            i++;
            j++;
        }
        else {
            j = ne[j];
            if(j == 0) {
                j++;
                i++;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cout.tie(nullptr);

    cin >> n >> m >> q;

    memset(res, 0, sizeof(res));

    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i ++) {
        cin >> b[i];
    }

    getNext(m);

    search(n, m);

    int x, y;
    for (int i = 0; i < q; i ++) {
        ans = 0;
        cin >> x >> y;
        for (int j = x; j <= y; j ++) {
                if(j + m - 1 <= y)
                ans += res[j][j + m - 1];
        }
         cout << ans << "\n";
    }
   
    return 0;
}