最长的电影

题干

小码哥在看电影，由于电影实在是太无聊了，他决定对电影进行一些改编。

一个电影 S 由 n 个情绪构成，每个情绪由一个大写的英文字母表示。小码哥有一些希望改编的片段，每个片段都由 l 个情绪构成。

如果在电影 S 中存在一个长度为 l 的子片段与小码哥的改编片段最多有两个情绪不相同，这个改编片段就是成功的。

请你计算出小码哥改编成功的片段数量。

格式

输入格式

第一行输入三个整数 n ( $1 \leq n \leq 2 \times 10^4$ ), m ( $1 \leq m \leq 10^5$ ), l ( $1 \leq l \leq \min(100, n)$ )，分别表示电影的长度、小码哥希望改编的片段个数以及片段的长度。

第二行包含一个长度为 n 的仅包含大写字母的字符串 S，表示电影的情绪构成。输入保证 S 随机生成。

随后 m 行，每行包含一个长度为 l 的仅包含大写字母的字符串，表示一个改编片段。不保证片段是随机生成的，且在生成片段时 S 已知。

输出格式 输出小码哥最终改编成功的片段数量。

示例 1

输入：

5 3 4 ABCDE BCDE BDDC AEEE

输出：

2

思路

题目就是说，从给定的影片 S 中取字字符串，如果某个子字符串与下面给出的某个字符串之多有两个不同，则匹配成功。最后给出匹配的总数。

直接暴力匹配是 $O(n m l)$，会爆。

这里的技巧是先匹配点位，再具体匹配。具体而言，可以把每个待匹配的字符串切成三段。因为至多有两个不同，因此三段里必然至少有一段要和源电影完全匹配。因此，可以用 $O(n l)$ 的复杂度去匹配点位（打 map 的话可以是 $O(n)$ ），然后再用 $O(m l)$ 的复杂度去测试是否满足两个以下不同字符的要求。

代码

#include <bits/stdc++.h>
using namespace std;

/**
 * 计算两个长度为 len 的字符串 s 和 t 在对应位置上不同的字符数。
 */
int countDifferences(const string &s, const string &t, int len) {
    int diff = 0;
    for(int i = 0; i < len; i++) {
        if(s[i] != t[i]) diff++;
        if(diff > 2) break; // 超过2个就可以提前停止
    }
    return diff;
}

int main(){
    // 读入 n, m, l
    int n, m, l;
    cin >> n >> m >> l;

    // 读入电影情绪串 S
    string S;
    cin >> S;

    // 如果片段长度小于3，那么“最多允许2处不同”就意味着无论什么片段都能匹配上
    // 因为长度1最多只会有1处不同，长度2最多也就2处不同
    if(l < 3) {
        cout << m << "\n"; // 直接全部成功
        return 0;
    }

    // 三段的长度 w
    int w = l / 3;

    // --- 第一步：记录 S 中所有“长度为 w 的子串”出现的起始位置 ---
    // map:  key   = S中某个长度为w的子串
    //       value = 该子串在S中出现的所有起始下标
    unordered_map<string, vector<int>> posMap;
    posMap.reserve(n); // 预留空间（非必须）
    for(int i = 0; i + w <= n; i++){
        string subW = S.substr(i, w);
        posMap[subW].push_back(i);
    }

    // --- 第二步：依次读取每个改编片段，判断是否成功 ---
    int answer = 0; // 统计成功的片段数

    while(m--){
        string T;
        cin >> T;

        // 将改编片段 T 分成3段 s1, s2, s3
        // 注意：l/3 的结果若有小数会被截断，题解中要求 l <= min(100, n)，
        // 一般情况下 l 可以被3整除或接近整除，这里先照题解思路写。
        string s1 = T.substr(0,      w);
        string s2 = T.substr(w,      w);
        string s3 = T.substr(2 * w,  w);

        bool success = false; // 标记当前片段是否能成功匹配

        // （1）若 s1 在 S 中出现，则枚举它所有出现位置 st
        //     s1 对应 T 的前 w 个字符 => 在 S 中起点 st => S[st...(st+w-1)]
        //     整个 T 就对应 S[st...(st+l-1)]
        //     需保证 st + l <= n，否则越界
        if(!success && posMap.count(s1)){
            for(int st : posMap[s1]) {
                if(st + l <= n) {
                    // 检查完整长度l的子串是否与T差异不超过2
                    if(countDifferences(S.substr(st, l), T, l) <= 2) {
                        success = true;
                        break;
                    }
                }
            }
        }

        // （2）若还没成功，则看 s2
        //     s2 是 T 的中间 w 个字符 => 对应在 S 中的位置可能是 st => T 整体应对齐 st-w
        //     因为 T[0..w-1] 对应 S[st-w..st-1]
        if(!success && posMap.count(s2)){
            for(int st : posMap[s2]) {
                int startPos = st - w; // 对齐整段 T 的开头
                if(startPos >= 0 && startPos + l <= n) {
                    if(countDifferences(S.substr(startPos, l), T, l) <= 2) {
                        success = true;
                        break;
                    }
                }
            }
        }

        // （3）若还没成功，则看 s3
        //     s3 对应 T 的最后 w 个字符 => 在 S 中出现的位置 st => T 整体应对齐 st-2*w
        if(!success && posMap.count(s3)){
            for(int st : posMap[s3]) {
                int startPos = st - 2*w;
                if(startPos >= 0 && startPos + l <= n) {
                    if(countDifferences(S.substr(startPos, l), T, l) <= 2) {
                        success = true;
                        break;
                    }
                }
            }
        }

        // 如果三段检查完依旧 success == false，说明找不到合适的子串
        if(success) answer++;
    }

    // 输出改编成功的总数
    cout << answer << "\n";
    return 0;
}