P8085

orzws · 2022-11-03 09:01:33 · 题解

看了题解的代码全都可以被讨论区的这组数据hack掉

输入：
a a a b c d d e f $
x x y z $

输出
2

被阴了好久，于是来写一篇题解(

看到字符匹配可以想到kmp，但是本题中要求的与具体的单词无关，所以我们可以把原单词直接用map离散化，然后记录一下上一个出现的数字出现的位置。然后我们就会发现有两个问题要解决：

• 如何快速匹配（更改kmp数组的含义来满足本题的失配跳跃）
• 如何判断是否可以匹配

对于第一个问题，可以想到将原本的 [1,L] 与 [x-L+1,x] 字符相同的意义改为 [1,L] 与 [x-L+1,x] 在本题解密的意义下相同

对于第二个问题，我们记 ls1[x] 为文本串为x在与上一个出现的距离， ls2[x] 为模式串，若第一次出现则距离为inf，fl为单词离散化后的数组，我们可以分讨一下,

• 如果 ls2[j] 为 inf，则 ls1[i] 必须大于等于j才能满足条件
• 如果 ls2[j] 不为 inf，则 fl[i-ls2[j]] 要等于 fl[i] 才能满足条件

然后我们按照将判断函数套用上方的分讨即可

其他题解中会被hack的主要原因是因为在求kmp数组时直接用 ls2 去匹配，但是这样其实是错的，我们在求kmp数组时要考虑清楚他的定义与匹配方式（上方的分讨），直接判断是否相等显然就没有考虑清楚匹配方式

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>

using namespace std;

#define ll long long

const int N = 1e6+7;
const int inf = 1e9;
string s;
int t1,t2,tp1,tp2,ls1[N],ls2[N],l[N],fl1[N],fl2[N],kmp[N];
map <string,int> mp;

void solve(int las[], int fl[], int &t) { 
    mp.clear(); for(int i = 1; i <= 1000000; i ++ ) l[i] = -inf;
    int tp = 0;
    for(int i = 1; cin >> s && s[0] != '$'; i ++ ) {
        t++;
        if(!mp[s]) mp[s] = ++tp; 
        int x = mp[s]; fl[i] = x;
        if(l[x] == -inf) las[i] = inf;
        else las[i] = i-l[x]; l[x] = i;
    }
}

bool check(int i, int j) {
    if(ls2[j+1] == inf && ls1[i] < j+1) return false;
    if(ls2[j+1] != inf && fl1[i] != fl1[i-ls2[j+1]]) return false;
    return true;
}

bool pd(int i, int j) {
    if(ls2[j+1] == inf && ls2[i] < j+1) return false;
    if(ls2[j+1] != inf && fl2[i] != fl2[i-ls2[j+1]]) return false;
    return true;
}

int main() {
    solve(ls1, fl1, t1);
    solve(ls2, fl2, t2);
    int j = 0;
    for(int i = 2; i <= t2; i ++ ) {
        while(!pd(i, j) && j) j = kmp[j];
        if(pd(i, j)) j++;
        kmp[i] = j;
    }
    j = 0;
    for(int i = 1; i <= t1; i ++ ) {
        while(j && !check(i, j)) j = kmp[j];
        if(check(i, j)) j++;
        if(j == t2) { cout << i-j+1; return 0; }
    }
}