基于k后缀统计的字符串生成程序性能优化求助

我正在完成一个编程任务，但性能无法达标，具体任务如下：

给定一个长度为n的单词S和整数参数k（1≤k<n），按规则生成S的扩展字符串S′：

• 每次新增字符时，取S′的最后k个字符作为后缀R；
• 统计S′中所有R出现位置后紧跟的字符的频率，选择频率最高的字符l（频率相同时选字母表靠前的；若R从未出现过则l='a'）；
• 将l追加到S′末尾。

输入格式：

• 第一行：四个整数n、k、a、b（2≤n≤1e6，1≤k<n，n<a<b<1e18，b-a+1≤1e6）；
• 第二行：长度为n的小写字母字符串S。

输出要求：输出S′中第a到第b位（包含两端）的字符序列，也就是追加的字符中最后b-a+1个。

示例输入：

11 3 12 13
abaaabababa

示例输出：ba

我已经实现了能正确生成字符串的程序，但当需要追加的字符数（b-n）极大（可达1e18）时，程序耗时过长。我们只需要输出最多1e6个字符，不需要生成全部字符串。测试中发现生成的字符串迟早会出现循环模式，应该不需要生成全部字符，求高效解法或相关思路。

[[nodiscard]] static std::string Model(
    const size_t n,
    const size_t k,
    const size_t a,
    const size_t b,
    std::string& word) noexcept(true)
{
    /* k-lettered substring -> character after the substring -> count */
    std::unordered_map<std::string, std::unordered_map<char, size_t>> occurences;

    for (size_t i{ 0U }; i < n - k; ++i)
        /* Extract a k-lettered substring at position i -> extract the letter after it -> increase count */
        ++occurences[word.substr(i, k)][word[i + k]];

    std::string lettersToPrint{};
    for (size_t i{ 0U }; i < (b - n) /* Do we really have to generate all of them? */; ++i)
    {
        /* k-lettered substring at the end of the "word". */
        std::string suffix(word.substr(word.length() - k, k));

        /* Detect the most popular character occurring after each suffix substring. */
        size_t mostPopularSuffixAppendLetterCount{ 0U };
        char mostPopularSuffixAppendLetter{ 'a' };

        for (char j{ 0 }; j < 26; ++j)
        {
            // careful! works with ASCII!!!
            const char currentCharacter{ char('z' - j) };
            const auto currentCharacterCount{ occurences[suffix][currentCharacter] };

            if (currentCharacterCount >= mostPopularSuffixAppendLetterCount)
            {
                mostPopularSuffixAppendLetterCount = currentCharacterCount;
                mostPopularSuffixAppendLetter = currentCharacter;
            }
        }

        word += mostPopularSuffixAppendLetter;

        if ((b - n) - i <= b + 1 - a)
            lettersToPrint += mostPopularSuffixAppendLetter;
    }

    return lettersToPrint;
}

int main()
{
    size_t n{ 65 }, k{ 2 }, a{ 67 }, b{ 783 };
    std::string word{ "ffdedffddfdefedddfdfddfddeedfdededddffeefffdeedfeddeddddfeefdffee" };

    assert(Model(n, k, a, b, word) == "dfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddfdeddf");

    return 0;
}

核心思路是利用状态循环：因为每次生成下一个字符的状态由当前的k长度后缀决定，而k长度的小写字母组合最多有26^k种可能（实际会远少于这个数，因为很多组合不会出现），所以状态必然会重复，一旦重复就会进入循环。我们可以：

• 记录状态轨迹：每个状态是当前的k长度后缀，同时记录该状态出现时的位置（即S′的长度）以及生成的字符。
• 检测循环：当某个状态第二次出现时，就找到了循环的起点和长度。比如状态R第一次出现在位置pos1，第二次出现在pos2，那么循环长度就是pos2 - pos1，循环的字符序列就是从pos1到pos2-1生成的字符。
• 跳过循环部分：
  1. 先生成到进入循环前的所有字符，直到当前位置接近a；
  2. 如果a在循环开始前，直接生成到b对应的位置；
  3. 如果a进入了循环，计算循环的偏移量，直接从循环序列中取对应的字符，不需要逐个生成。

具体优化步骤 #

1. 状态编码优化：不要用std::string存储k长度后缀，改用整数编码（比如把每个字母映射为0-25，k长度后缀转换为26进制数，用64位整数或多整数组合存储），减少字符串操作的开销，同时加速状态的哈希和比较。
2. 预处理转移规则：提前为每个可能的状态（k长度后缀）计算好下一个要生成的字符——遍历初始S的所有k长度子串，统计每个后缀的后续字符频率，直接确定每个状态对应的唯一下一个字符，生成时直接查表即可，避免每次遍历26个字母。
3. 循环检测与利用：用哈希表记录每个状态第一次出现的位置和对应的输出字符序列索引，一旦发现重复状态，立即计算循环的起始位置和长度。之后对于超出循环起始位置的目标区间，直接通过循环的周期性计算出需要的字符，跳过中间大量的生成步骤。
4. 按需生成字符：只生成到能覆盖a到b区间的字符即可，不需要生成全部扩展字符串，重点是利用循环快速定位到目标位置的字符。

• 替换std::unordered_map<std::string, ...>为基于整数编码的哈希表，消除字符串拷贝和哈希计算的开销；
• 预处理每个状态的转移字符，避免每次生成时重复计算频率最大值；
• 检测循环并利用周期性跳过多余生成步骤，将时间复杂度从O(b-n)降低到O(n + 循环长度 + b-a)，完全适配b-n极大的场景。

内容的提问来源于stack exchange，提问作者questionaire