E. Martian Strings - 题解

比赛与标签

比赛: Codeforces Round 106 (Div. 2) 标签: string suffix structures, strings 难度: *2300

火星人的奇妙早晨喵~

主人，早上好喵~！今天我们来帮一位懒洋洋的火星人解决一个有趣的难题吧！(ฅ'ω'ฅ)

这位火星人有一排眼睛，当他醒来时，他会睁开两段不重叠的连续区间的眼睛。他眼睛上的眼罩内侧都写着一个大写字母，所以他睁开眼睛后，会按从左到右的顺序看到一个由两部分拼接起来的字符串。

我们有一个长长的主字符串 s，代表所有眼罩上的字母。还有 m 个火星人认为很“美丽”的单词 p。

我们的任务就是，对于每一个美丽的单词 p，判断它能否通过火星人睁开两段不重叠眼睛的方式，由主字符串 s 的两段子串拼接而成。最后，我们要数出总共有多少个不同的美丽单词可以这样形成。

举个栗子呐：如果 s = ABCBABA，一个美丽单词是 ABBA。火星人可以睁开 [1, 2] 区间的眼睛看到 AB，再睁开 [6, 7] 区间的眼睛看到 BA。因为 2 < 6，这两段不重叠，拼接起来就是 ABBA！所以 ABBA 就是一个可以被看见的美丽单词。

KMP的双向奔赴！

这个问题看起来是要我们在一个大字符串 s 中，找到一个美丽串 p 的前缀和后缀，并且它们在 s 中的位置要满足不重叠的条件，对吧喵？

如果我们暴力枚举 p 的所有分割方式，再暴力地在 s 中寻找这两部分，那肯定会慢得像蜗牛一样，会被 TLE 大魔王抓走的！所以，我们需要更聪明的办法，这就要请出我们的字符串匹配神器——KMP算法啦！

我们的核心思路是这样的：对于每个美丽单词 p，我们将它拆分成一个非空前缀 A 和一个非空后缀 B。我们的目标，就是在 s 中找到 A 和 B，使得 A 的出现位置完全在 B 的出现位置之前。

为了让 A 和 B 不重叠的概率最大化，我们应该让 A 尽可能地出现在 s 的最左边，同时让 B 尽可能地出现在 s 的最右边。

第一步：寻找最靠左的前缀 A

我们可以用 KMP 算法来处理这个问题！对于一个模式串 p，KMP 算法在匹配过程中，实际上能告诉我们 p 的所有长度的前缀在主串 s 中的匹配情况。

我们可以定义一个数组 F，F[k] 用来记录 p 的长度为 k 的前缀 p[0...k-1] 在 s 中第一次出现的起始位置。我们只需要跑一遍标准的 KMP 匹配，当匹配到长度为 j 的前缀时，如果 F[j] 还是初始值，就立刻记录下当前的起始位置。这样就能保证我们找到的是最靠左的匹配位置啦！

第二步：寻找最靠右的后缀 B

找最右边的后缀有点麻烦，但这里有一个超级喵喵赞的技巧——把所有东西都反过来！

我们将主串 s 和模式串 p 都进行反转，得到 s_rev 和 p_rev。现在，寻找 p 的一个后缀 B 就等价于在 p_rev 中寻找一个前缀 B_rev（B 的反转）。在 s 中寻找 B 的最右出现位置，就等价于在 s_rev 中寻找 B_rev 的最左出现位置！

看吧，问题瞬间就和第一步一样了！我们可以用同样的方法，再跑一遍 KMP，找到 p_rev 的所有前缀在 s_rev 中的最左出现位置，并记录在数组 H 中。

第三步：合并结果，检查重叠

现在我们有了两个法宝：

F[k]：p 的长度为 k 的前缀在 s 中的最左起始位置。
H[len]：p 的长度为 len 的后缀（在反转串中是长度为 len 的前缀）在 s 中的最右匹配的起始位置。

我们遍历 p 的所有可能的分割点 k（k 从 1 到 |p|-1）：

前缀 A 的长度是 k。它在 s 中的匹配区间是 [F[k], F[k] + k - 1]。
后缀 B 的长度是 L-k（L 是 p 的总长）。它的反转串是 p_rev 中长度为 L-k 的前缀。
这个反转的后缀在 s_rev 中的最左匹配起始于 H[L-k]。我们需要把它换算回 s 中的坐标。s_rev 中从 H[L-k] 开始的匹配，对应到原串 s 中，其起始位置是 n - (H[L-k] + (L-k)) (这里 n 是 s 的长度)。
现在，我们只需要检查前缀 A 的结束位置是否小于后缀 B 的开始位置： F[k] + k - 1 < n - (H[L-k] + (L-k))
只要有任何一个分割点 k 满足这个条件，就说明这个美丽的单词 p 是可以被火星人看到的！我们立刻把它计数，然后就可以开心地去检查下一个美丽单词啦，喵~

猫娘的代码魔法~

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s;
    int m;
    cin >> m;
    vector<string> words(m);
    for (int i = 0; i < m; i++) {
        cin >> words[i];
    }

    int n = s.size();
    int ans = 0;

    // 对每一个美丽单词进行检查
    for (const string& p : words) {
        int L = p.size();
        // 长度小于2的单词无法被分割成两个非空部分
        if (L < 2) 
            continue;

        // --- 第一步: KMP 寻找 p 的所有前缀在 s 中的最左出现位置 ---
        
        // F[j] 存储 p 的长度为 j 的前缀在 s 中首次出现的起始下标
        vector<int> F(L + 1, -1);
        
        // 1. 构建 p 的 fail 数组 (前缀函数)
        vector<int> fail(L, 0);
        int j = 0;
        for (int i = 1; i < L; i++) {
            while (j > 0 && p[i] != p[j]) {
                j = fail[j - 1];
            }
            if (p[i] == p[j]) {
                j++;
            }
            fail[i] = j;
        }

        // 2. KMP匹配，填充 F 数组
        j = 0;
        for (int i = 0; i < n; i++) {
            while (j > 0 && s[i] != p[j]) {
                j = fail[j - 1];
            }
            if (s[i] == p[j]) {
                j++;
            }
            // 如果长度为 j 的前缀是第一次找到，就记录它的起始位置
            if (F[j] == -1) {
                F[j] = i - j + 1;
            }
        }
        
        // --- 第二步: 反转字符串，寻找 p 的所有后缀在 s 中的最右出现位置 ---

        // 1. 反转模式串 p 和主串 s
        string p_rev = p;
        reverse(p_rev.begin(), p_rev.end());
        string s_rev = s;
        reverse(s_rev.begin(), s_rev.end());
        
        // H[j] 存储 p_rev 的长度为 j 的前缀在 s_rev 中首次出现的起始下标
        vector<int> H(L + 1, -1);
        
        // 2. 构建 p_rev 的 fail 数组
        vector<int> fail_rev(L, 0);
        j = 0;
        for (int i = 1; i < L; i++) {
            while (j > 0 && p_rev[i] != p_rev[j]) {
                j = fail_rev[j - 1];
            }
            if (p_rev[i] == p_rev[j]) {
                j++;
            }
            fail_rev[i] = j;
        }

        // 3. KMP匹配，填充 H 数组
        j = 0;
        for (int i = 0; i < n; i++) {
            while (j > 0 && s_rev[i] != p_rev[j]) {
                j = fail_rev[j - 1];
            }
            if (s_rev[i] == p_rev[j]) {
                j++;
            }
            // 同样，只记录第一次找到的位置
            if (H[j] == -1) {
                H[j] = i - j + 1;
            }
        }

        // --- 第三步: 检查是否存在不重叠的分割 ---
        bool found = false;
        // 遍历所有可能的分割点 k (前缀长度为 k)
        for (int k = 1; k < L; k++) {
            // 前缀长度为k, 后缀长度为 L-k
            if (F[k] == -1 || H[L - k] == -1) {
                // 如果前缀或后缀在 s 中不存在，跳过这个分割
                continue;
            }
            // 前缀部分在 s 中的结束位置 (0-indexed)
            int end_A = F[k] + k - 1;
            // 后缀部分在 s 中的开始位置 (0-indexed)
            // H[L-k] 是在 s_rev 中的起始位置 (0-indexed)
            // 换算回 s 中的坐标
            int start_B = n - (H[L-k] + (L - k));
            
            // 检查是否不重叠
            if (end_A < start_B) {
                found = true;
                break; // 找到一个就行了！
            }
        }

        if (found) {
            ans++;
        }
    }

    cout << ans << endl;
    return 0;
}

算算时间喵！

时间复杂度: O(Σ|pᵢ| + m * |s|) 的说。对于 m 个美丽单词中的每一个，我们都需要：
1. 构建 p 和 p_rev 的 fail 数组，耗时 O(|p|)。
2. 在 s 和 s_rev 上进行KMP匹配，耗时 O(|s|)。所以处理一个单词的总时间是 O(|p| + |s|)。总的来说就是所有单词长度之和，再加上 m 次扫描主串 s 的时间。因为 m 和 |p| 都比较小，这个复杂度是完全可以接受的！
空间复杂度: O(|p|{max} + |s|) 的说。我们需要空间来存储 s_rev，这需要 O(|s|) 的空间。对于每个单词，我们还需要 p_rev、fail 数组、F 和 H 数组，这些都与 |p| 的最大长度有关，即 O(|p|)。所以总空间由这两部分主导。

喵喵小课堂~

这道题真是太棒了，把 KMP 算法玩出了花，主人你学会了吗？总结一下核心知识点呐：

KMP 算法的灵活应用: KMP 不仅仅是用来判断一个串是否在另一个串里出现过。它的 fail 数组和匹配过程蕴含了模式串所有前缀的匹配信息，非常强大！
正反串技巧: 这是字符串问题中的一个经典“大招”！当你需要处理后缀相关的问题，或者需要从字符串尾部开始匹配时，不妨试试把字符串整个反转过来。这样，后缀问题就变成了我们更熟悉的前缀问题，处理起来就顺手多啦！
预处理与组合: 我们的解法完美体现了“预处理”的思想。我们不是对每个分割点都去 s 中暴力查找，而是先通过两次 KMP 预处理出所有前缀和后缀的最优位置信息，最后再用一个简单的循环将这些信息组合起来进行判断，大大提高了效率。

希望这篇题解能帮到你，喵~！继续加油，算法的世界还有更多有趣的冒险在等着我们呢！(>ω<)ﾉ

E. Martian Strings - 题解 ​

比赛与标签 ​

火星人的奇妙早晨喵~ ​

KMP的双向奔赴！ ​

猫娘的代码魔法~ ​

算算时间喵！ ​

喵喵小课堂~ ​