CodeForces1016B-Segment Occurrences题解

流光萤影 · 2023-08-07 19:24:24 · 题解

前言：

本题解使用语言：C++14 (GCC 9)。

引用链接：https://article.itxueyuan.com/KAZQpD。

正文：

基本思路：前缀和。

代码实现：

遍历一遍字符串 a，用数组 map 记录前缀和，map _ i 为 a _ {[1,i]} 中 b 的个数：

for(int i = 0;i < a.length();i++)
{
    if(i+1 < b.length()) continue;
    if(a.substr(i+1-b.length(),b.length()) == b) _map[i+1]++;
    _map[i+1] += _map[i];
}

根据前缀和思想，得出核心关系：a _ {[l,r]} 中 b 的个数为 map _ r - map _ {l + |b| - 2}。

于是输出代码也实现了：

for(;q;q--) cin >> l >> r,cout << (r-l+1 < b.length()?0:_map[r]-_map[l+b.length()-2]) << "\n";

AC 代码：

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int _map[1005],n,m,q,l,r,first;
string a,b;
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m >> q >> a >> b;
    for(int i = 0;i < a.length();i++)
    {
        if(i+1 < b.length()) continue;
        if(a.substr(i+1-b.length(),b.length()) == b) _map[i+1]++;
        _map[i+1] += _map[i];
    }
    for(;q;q--) cin >> l >> r,cout << (r-l+1 < b.length()?0:_map[r]-_map[l+b.length()-2]) << "\n";
    return 0;
}