c++ - 如何在给定起点和终点的字符串中查找子字符串的出现次数？

Question

给定一个字符串和一个子字符串，以及起点和终点的索引，我希望能够找到该子字符串在边界中出现的次数。例如，给定字符串“ACACTACG”，我想找到子字符串“AC”从 3 到 7 的出现次数(如果第一个索引为 1)。上面的示例产生输出 2。从 3 到 7，我们有“ACTAC”，其中子字符串“AC”出现了 2 次。我似乎无法用 C++ 编写代码；

这是AtCoder初学者竞赛122的C题:https://atcoder.jp/contests/abc122/tasks/abc122_c

我实际上设法将其编码出来，但超过了时间限制。我需要一种更简单的方法。

这是我提交的 TLE 结果:

#include <iostream>

using namespace std;

int main()
{
    int N, Q;
    string s;
    cin >> N >> Q >> s;

    for(int i = 0; i < Q; i++)
    {
        int l, r;
        cin >> l >> r;
        if(l >= r)
        {
            cout << 0 << endl;
            break;
        }
        int count = 0;
        for(int j = l - 1; j < r; j++)
        {
            if(s[j] == 'A' && s[j + 1] == 'C' && j != r - 1)
            {
                count++;
                j++;
            }
        }
        cout << count << endl;
    }

    return 0;
}

经过一些数学运算，我发现我得到 TLE 的原因是因为我的代码大约有 10^10 条指令，而 2 秒的时间限制只能执行大约 2 * 10^8 条指令。

Answer 1

字符串 N 对于所有查询都是相同的，您只需要查找模式 AC。这意味着您可以为答案预先计算一个查找表，并避免为每个查询迭代 N。

查找表将包含自字符串开头以来 AC 的出现次数。对于 ACACTACG，它将是

A={0,1,1,2,2,2,3,3}

这很有帮助，因为“x 和 y 之间出现 AC 的次数”与“y 之前的出现次数相同，除了 x 之前的那些”。每当您必须回答有关范围的问题时，这样的表格通常很有用

例如，要回答查询 3,7，您需要计算 A[7]-A[3] = 3-1 = 2。