题解：P11705 「KTSC 2020 R1」字符串查找

· · 题解

方法 / 建议添加标签 / 前置芝士

更新

update 2025.3.1：更正了错误的时空复杂度（之前没有用题目中给定的字母）。

题意简述

可以看到，这就是一个 KMP 问题，就是把相等关系改变了一下。简单点说就是：

如果两个长度相同的字符串各自串中的字符相等关系相同，则认为这两个字符串实际上相同。

这使得我们不必关心字母本身是什么，只用关心相同的字母在字符串中的位置。

解法

一个结论

向两个实际上相同的字符串末尾各添加一个字符，只要两个添加的字符在各自串内第一次出现的位置相同（或者都没有在串内出现过），那么添加单字符后的两个字符串仍然本质上相同。

证明

显而易见。

如果这两个字符在各自串内第一次出现的位置相同，因为两个字符串本来就是本质上相同的，可以得知与这两个字符相同的字符在各自串内的位置都是一致的，所以本质上相同的性质并没有被破坏。证毕。

所以……

思路

维护 26 个队列。

在进行 KMP 时将当前字符在字符串中的位置加入对应的队列，每个队列分别存储所有对应字母的下标。

另外，在添加下一个字符计算字串 border 时，会发生无法匹配导致需要减小长度再次尝试的情况，这时需要及时将不在当前尝试匹配后缀中的字符下标删掉。

因为加入顺序的原因，每个队列中的下标都是严格单调递增的，所以队首元素必然是当前要尝试匹配的后缀中对应字母第一次出现的下标，并且可以保证要删掉的字符下标一定是队首元素（因为是从前往后遍历，前面的字符已经都删完了）。

所以我们就可以在 O(1) 的时间内获取当前要尝试匹配的后缀内任意字母第一次出现的下标。

另外还要预处理出每一个字母在字符串中第一次出现的位置，用于查询前缀中任意字母第一次出现的下标。

这样我们就可以 O(1) 比较插入新字符后，两个字符串是否仍然本质上相同。

然后套一个 KMP 板子就行了。

可以看到每个字符一定只会进队出队一次，而 KMP 的复杂度也只有 O(N + M)，所以时间复杂度和空间复杂度就很明显了：

时间复杂度：O(N + M)。

空间复杂度：O(N + M)。

注意事项——KMP 的分隔符

在 KMP 中，我们求 border 时会在模式串和文本串之间加一个不在字符集中的分隔符（我用的是 @），需要特判分隔符，及时清除队列中的所有内容，且出现这个字符时不能认为两个字符串相等（血泪经历~~）。

代码

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

queue <int> q[26];
int fir[26];

inline bool check(char &front,char &back,int front_end,int back_start){
    if(front == '@' || back == '@') return false;
    const bool front_none = !fir[front - 'a'] || fir[front - 'a'] > front_end;
    const bool back_none = q[back - 'a'].empty();
    if(front_none && back_none) return true;
    if(front_none != back_none) return false;
    return fir[front - 'a'] == q[back - 'a'].front() - back_start;
}

inline int* const make(char x[],const int len){
    int *const ans = new int[len],now;
    for(int i = 0;i < len;i++)
        ans[i] = 0;
    for(int i = 1;i < len;i++)
        if(!fir[x[i] - 'a'])
            fir[x[i] - 'a'] = i;
    for(int i = 2;i < len;i++){
        if(x[i] == '@'){
            for(int j = i - ans[i - 1];j < i;j++)
                q[x[j] - 'a'].pop();
            continue;
        }
        for(now = ans[i - 1];!check(x[now + 1],x[i],now,i - 1 - now);now = ans[now])
            for(int j = i - now;j < i - ans[now];j++)
                q[x[j] - 'a'].pop();
        q[x[i] - 'a'].push(i);
        ans[i] = now + 1;
    }
    return ans;
}

int findP(char T[], char P[], int N, int M){
    char str[N + M + 5];
    str[0] = ' ';
    strcpy(str + 1,P);
    str[M + 1] = '@';
    strcpy(str + M + 2,T);
    int *const num = make(str,M + N + 2),ans = 0;
    for(int i = 0;i < M + N + 2;i++)
        if(num[i] == M)
            ans++;
    return ans;
}

后记

感觉这个题出的很好，很有意思，但是作为 KOI 的第一题是不是有点简单？难度就相当于难一点的绿，评蓝也没问题。

我好像在 AC 记录里看到了哈希的做法，但是很慢，这个还是留给后人吧。

64ms，轻松跑到最优解（2025.2.28）。

一个问题：为什么这个题要开 3s 的时限？韩国的测评姬不会连 10^6 的运算量都跑不过去吧……

都看到这里了，想想你应该干点什么……

附：如果您参考了本篇文章（不嫌弃我的啰嗦），十分感谢！