B. Segment Occurrences

题目链接

Educational Codeforces Round 48 (Rated for Div. 2)--B. Segment Occurrences

题解

简单题,题意大概是给定两个字符串和一些区间,求出在 a 串的指定区间中 b 串的数量。
由于数据规模较小,对 b 串得到 next 数组后直接暴力套到 a 串指定区间的字串上即可。

代码

#include <iostream>
#include <string>
using namespace std;
int next1[1005];
int n, m, q;
void getnext(string str)
{
    next1[0] = -1;
    int k = -1, j = 0;
    while (j<str.size() - 1) {
        if (k == -1 || str[k] == str[j]) {
            k++; j++;
            next1[j] = k;
        }
        else {
            k = next1[k];
        }
    }
}
int main()
{
    cin >> n >> m >> q;
    string str1, str2;
    cin >> str1 >> str2;
    getnext(str2);
    while (q--) {
        int cnt = 0;
        int l, r; 
        cin >> l >> r;
        string str3 = str1.substr(l - 1, r - l + 1);
        int i = 0, j = 0;
        while (i < str3.size()) {
            if (j == -1 || str3[i] == str2[j]) {
                if (j == str2.size() - 1) {
                    cnt++; j = next1[j];
                    continue;
                }
                i++; j++;
            }
            else {
                while (j >= 0 && str2[j] != str3[i])
                    j = next1[j];
            }
        }
        cout << cnt << endl;
    }
    return 0;
}

标签: implementation, brute force

添加新评论