KMP（3）

例 2 题目链接：HDOJ1711

这个题目的大意就是给你一个整数数组 A=[A1, A2, … AN] 和一个整数数组 B=[B1, B2, … BM]，让你找到一个位置 K 使得从 A [K] 开始的 M 个整数与 [B1, B2, … BM] 相等。如果没有满足条件的位置 K 就输出 - 1

这其实就是一个整数版的 KMP。我们之前讲 KMP 的背景都是字符串匹配，其实也可以拿来做数组序列匹配。只要把整数相等对应成字符相等就可以了

#include <cstring>
#include <cstdio>
using namespace std;
int nxt[1000001];
int ans,t;
int p[1000001],s[1000001];
int n,m;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        ans = -1;
        scanf("%d %d",&n,&m);
        for(int i = 1;i <= n;i++)
            scanf("%d",&s[i]);
        for(int i = 1;i <= m;i++)
            scanf("%d",&p[i]);
        nxt[0] = -1;
        int j = -1;
        for(int i = 1;i <= m;i++)
        {
            while(j >= 0 && p[j + 1] != p[i])
                j = nxt[j];
            nxt[i] = ++j;
        }
        j = 0;
        for(int i = 1;i <= n;i++)
        {
            while(j >= 0 && p[j + 1] != s[i])
                j = nxt[j];
            if(++j == m)
            {
                ans = i - m + 1;
                break;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

例 3 题目链接：HDOJ2087

这道题目的大意是给定两个字符串 P 和 S。问 P 能从 S 中剪出来多少次。这道题看上去与上一节 hihoCoder #1015 题类似。但是其实是有一个关键条件不一样，这道题不允许剪出来 P 在 S 中重叠。比如在之前的题目中 ADA 在 ADADADA 中出现了 3 次，本题中就只能剪出来 2 次。这道题的样例也告诉你，从 aaaaaa 中最多剪出来 3 个 aa

这道题有两种思路。第一种思路是先不管三七二十一，用 hihoCoder #1015 中的匹配方法，把所有出现 P 的位置都求出来，存在一个 vector<int> start_pos 里：

for(int i = 1;i <= n;i++)
{
    while(j >= 0 && p[j + 1] != s[i])
        j = nxt[j];
    if(++j == m)
    {
        start_pos.push_back(i - m + 1);
        j = nxt[j];
    }
}

假如输入是 aaaaaa 和 aa，那么 start_pos 中保存的就是 [1, 2, 3, 4, 5]。现在我们的问题就变成要从 start_pos 中选出尽量多的整数，并且保证相邻的两个整数差不小于 P.len。比如上面的例子中就应该选出 [1, 3, 5]

这个问题是可以贪心选的。大致思路就是一定选第一个最小的整数，然后从小到大检查每一个整数，如果能选（与上一个差不小于 P.len）就一定选，不能选再看下一个。伪代码如下：

Last_Pick = -P.len
Cnt = 0
For i:start_Pos
    If i - Last_Pos >= P.len
        Last_Pick = i
        Cnt++
Print Cnt

第二种思路。这种思路是建立在贪心算法基础上的。假设 S [L..L+P.len-1] 是 P 第一次出现的位置。根据贪心的思路，这个 S [L..L+P.len-1] 是一定要被剪出来的。在之前的题目中，找到一个完整匹配 j==m 的时候是令 j = next [j] (也就是 j=next [m])，让 S [i] 与 P [next [m]+1] 继续匹配。这里 S [i] 就是 S [L+P.len]

; 本题要避免剪出重叠的 P，要把 S [L..L+P.len-1]” 剪掉 “，显然剪掉之后 S [L+P.len] 只能从 P [1] 开始匹配起了，而不能从 P [next [m]+1] 开始了。所以我们直接把 j = next [j] 改成 j = 0 即可让 KMP 按我们的要求避免重叠

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int nxt[1000001];
int ans,n,m;
char p[1000001],s[1000001];
int main()
{
    scanf("%s",s + 1);
    while(strcmp(s + 1,"#") != 0)
    {
        scanf("%s",p + 1);
        n = strlen(s + 1);
        m = strlen(p + 1);
        ans = 0;
        nxt[0] = -1;
        int j = -1;
        for(int i = 1;i <= m;i++)
        {
            while(j >= 0 && p[j + 1] != p[i])
                j = nxt[j];
            nxt[i] = ++j;
        }
        j = 0;
        for(int i = 1;i <= n;i++)
        {
            while(j >= 0 && p[j + 1] != s[i])
                j = nxt[j];
            if(++j == m)
            {
                ans++;
                j = 0;
            }
        }
        cout << ans << endl;
        scanf("%s",s + 1);
    }
    return 0;
}

上面的代码同上一节 hihoCoder #1015 题除了处理输入部分之外，就只有 27 行不一样。这道题的代码 27 是直接 j = 0，从而强制下一个字符 S [i] 从 P [1] 开始匹配。第二个思路需要对 KMP 的理解更加清楚，才能更加灵活的运用

例 4 题目链接：hihoCoder1625

题目大意是给定两个字符串 A 和 B，请你求出字符串 A 最少重复几次才能使得 B 是 A 的子串。例如 A="hiho"，B="hohihohi"。则 A 重复 3 次之后变为 "hihohihohiho"，这时 B 是 A 的子串。如果没有解输出 - 1

这题降低时间复杂度的关键是一次性得到足够长的 S，进行 KMP；而不能从一个比较短的 S 开始尝试 KMP，匹配不成就在 S 后面接一个 A，再匹配不成再接一个 A……

于是问题来了，S 多长才是足够长？这个问题的答案是 A.len+B.len。证明比较简单，留给大家自己思考。于是我们有一个伪代码：

S = 空串
While S.len < A.len + B.len
    S = S + A//+这里是字符串连接
L = KMP(B,S)
If L > 0
    Print L + B.len - 2 / A.len + 1//长度L + B.len - 1需要几个A拼起来
Else
    Print -1

不过这道题目还有一种更简单的实现方法。我们可以并不真的拼出一个字符串 S。而是 “假装” 有一个字符串 S。当我们 KMP 的过程中需要用的 S [i] 的时候，就用 A [(i-1) % A.len+1] 代替。代码如下：

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int nxt[1000001];
int ans,n,m,t;
char p[1000001],s[1000001];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s%s",s + 1,p + 1);
        n = strlen(s + 1);
        m = strlen(p + 1);
        ans = -1;
        nxt[0] = -1;
        int j = -1;
        for(int i = 1;i <= m;i++)
        {
            while(j >= 0 && p[j + 1] != p[i])
                j = nxt[j];
            nxt[i] = ++j;
        }
        j = 0;
        for(int i = 1;i <= n + m;i++)
        {
            char c = s[(i - 1) % n + 1];
            while(j >= 0 && p[j + 1] != c)
                j = nxt[j];
            if(++j == m)
            {
                ans = (i - 1) / n + 1;
                break;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

注意第 28 行这里的 s 实际上是题目中的 A。我们实际上并没有 S [i]，而是用 A 中的对应字符代替

例 5 题目链接：HDOJ2594

这道题目的大意是给定两个字符串 P 和 S，让你找一个最长的字符串 T 满足 T 是 P 的前缀，也是 S 的后缀

如果你对 KMP 的过程非常清楚的话，你会发现 KMP 用 P 去匹配 S 的过程中，如果 S [i] 匹配上了 P [j] 那就说明 P [1..j] 是 S [1..i] 的最长后缀，同时 P [1..j] 显然是 P 的前缀。所以我们只要找到第一个匹配上 S [n] 的 P [j] 的即可，这时 j 就是答案

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int nxt[1000001];
int ans,n,m,t;
char p[1000001],s[1000001];
int main()
{
    while(scanf("%s%s",p + 1,s + 1) != EOF)
    {
        n = strlen(s + 1);
        m = strlen(p + 1);
        nxt[0] = -1;
        int j = -1;
        for(int i = 1;i <= m;i++)
        {
            while(j >= 0 && p[j + 1] != p[i])
                j = nxt[j];
            nxt[i] = ++j;
        }
        j = 0;
        for(int i = 1;i <= n;i++)
        {
            char c = s[(i - 1) % n + 1];
            while(j >= 0 && p[j + 1] != c)
                j = nxt[j];
            if(++j == m)
            {
                if(i == n)
                    break;
                j = nxt[j];
            }
        }
        if(j == 0)
            cout << 0 << endl;
        else
        {
            p[j + 1] = 0;
            cout << p + 1 << ' ' << j << endl; 
        }
    }
    return 0;
}