算法能解决的问题

给定模式串$p$和主串$s$, 检查$s$中是否存在$p$串, 并且检查$p$串出现的位置

算法原理

• 假设给定字符串$s=ACAACA$
• 将不包含自身的前后缀列出, 找到最长的相等的前后缀, 也就是最长匹配真前后缀, 长度记为${\pi }_i$
• 然后将字符串的所有非空前缀全部列出来
  
  如果直接暴力求$\pi$, 算法时间复杂度$O(n^2)$, 需要进行优化

用递推的思想, 假设已经计算出了${\pi }_0\sim {\pi }_{i-1}$, 当前希望计算${\pi }_i$

令$j={\pi }_{i-1}$
对于当前情况, 如果$S[j]=S[i]$, 那么${\pi }_i={\pi }_{i-1}+1$

如果不相等, 找第二长的公共前后缀, 假设位置是$t$, 如果相等${\pi }_i={\pi }_t+1$, 如果不相等继续找第三长的

那么问题就变成了, 如何根据当前最长后缀找到第二长的前缀

$A,B,C$三段相等, 也就是

int j = ne[i - 1];
if (s[j] != s[i]) {
	j = ne[j - 1];
}

这样就可以在线性的时间复杂度内处理出${\pi }_i$数组

那么如何使用${\pi }_i$来解决字符串匹配的问题?
假设目标串是$S$, 给定的模式串是$P$, 可以进行拼接操作S' = P + # + S, 对新的字符串求一遍${\pi }_i$, 当${\pi }_i=P.size()$, 说明找到了模式串

为什么拆分写法需要将指针$j$清零?

• 实际上拼接字符串过程中的添加的特殊字符就是在$i$遍历到$S$串的时候, $j$需要重新指向$P$串的第一个前缀位置进行比对(主串可以理解为后缀)
• 如果不将$j$指针清零, 相当于模式串和主串直接拼接, 假设某一段模式串 + 某一段主串匹配上了某一段模式串的前缀, 这实际是违法的
• 总结来说, 将$j$指针清零相当于告诉ne数组, 后面不会再有更长的最长匹配真前后缀, 需要从头开始重新匹配, 这样符合我们希望将$p$串作为前缀, $s$串作为后缀的需求, 因此需要将$j$指针清零

算法步骤

• 根据int j = ne[i - 1]构建出ne数组
• 将模式串拼接到主串, 假设新的字符串是$s^{\prime }$, 在拼接后发现最长匹配真后缀的长度和模式串$p$相等, 相当于找到了模式串
• 如果不将模式串拼接到主串, 可以直接遍历主串, 但是需要将j = ne[i - 1]的j指针指向开头

例题

28. 找出字符串中第一个匹配项的下标

从原理出发的写法

#include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + 10;

class Solution {
public:
    int strStr(string haystack, string needle) {
        int m = needle.size();
        int ne[N] = {0};
        string new_s = needle + '@' + haystack;
        for (int i = 1; i < new_s.size(); ++i) {
            int j = ne[i - 1];
            while (j && new_s[j] != new_s[i]) j = ne[j - 1];
            if (new_s[j] == new_s[i]) ne[i] = j + 1;
            if (ne[i] == m) {
                return i - 2 * m;
            }
        };
        return -1;
    }
};

拆分写法

因为拆分之前两个字符串直接使用特殊字符连接, 拆分之后特殊字符消失, $j$需要清零, 特殊字符的作用就是将$j$移动到初始位置

#include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + 10;

class Solution {
public:
    int strStr(string s, string p) {
        int n = s.size(), m = p.size();
        int ne[N] = {0};

        for (int i = 1; i < m; ++i) {
            int j = ne[i - 1];
            while (j && p[j] != p[i]) j = ne[j - 1];
            if (p[j] == p[i]) ne[i] = j + 1;
        }

        for (int i = 0, j = 0; i < n; ++i) {
            while (j && p[j] != s[i]) j = ne[j - 1];
            if (p[j] == s[i]) j++;
            if (j == m) return i - m + 1;
        }
        return -1;
    }
};

最普遍的模板写法

#include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + 10;

class Solution {
public:
    int strStr(string s, string p) {
        s = ' ' + s, p = ' ' + p;
        int n = s.size(), m = p.size();
        int ne[N] = {0};

        for (int i = 2; i < m; ++i) {
            int j = ne[i - 1];
            while (j && p[j + 1] != p[i]) j = ne[j];
            if (p[j + 1] == p[i]) ne[i] = j + 1;
        }

        for (int i = 1, j = 0; i < n; ++i) {
            while (j && p[j + 1] != s[i]) j = ne[j];
            if (p[j + 1] == s[i]) j++;
            if (j == m - 1) return i - m + 1;
        }
        return -1;
    }
};