字符串匹配

前缀函数($\pi$函数)

定义

给定一个长为$n$字符串$S$，其前缀函数被定义为一个长度为$n$的数组$\pi$。其中$\pi$的定义是：如果子串$s[0...i]$有一对或多对相等的真前缀与后前缀，$\pi[i]$等于他们相等的最长长度，没有则为0.

具体实现

遍历字符串，每次都从最大的$\pi$开始比较。

vector<int> piFunction(string s)
{
	int n = s.length();
    vector<int> pi(n);
    for(int i=0;i<n;i++)
    {
		for(int j=i;j>=0;j--)
        {
			if(s.substr(0,j)==s.substr(i-j+1,i))
            {
                pi[i]=j;
                break;
            }
        }
    }
    return pi;
}

优化

当$s[i+1]=s[\pi[i]]$时很容易得到，对于$\pi[i+1]$我们知道他最大等于$\pi[i]+1$，所以在第二层循环中$j$可以从$\pi[i]+1$开始。

当$s[i+1]!=s[\pi[i]]$时，我们需要从$j^0=\pi[i]$不断往前寻找$j^{(k+1)}=\pi[i+1]$，即$s[i+1]=s[j^{k+1}]$。通过图片我们可以知道，经过对$\pi$的维护此时$A,B,C$段是完全相同的，所以当最后一个字符不匹配时代表对于当前的$j^{k}$其后面$\pi[j-1]$个数都不可能匹配。

这样我们可以将前面$j--$（此处为$k++$）的过程替换成$j=\pi[j-1]$。

vector<int> piFunction(string s)
{
    int n = s.length();
    vector<int> pi(n, 0);
    for (int i = 1; i < n; i++)
    {
        int j = pi[i - 1];
        while (j != 0 && s[i] != s[j])
            j = pi[j - 1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
    return pi;
}

KMP

给出一个长为$n$字符串$s$和一个文本$t$，求出$s$在$t$中的所有出现。

我们可以构造一个新字符串$cur=s+'\#'+t$其中$\#$为既不出现在$s$也不出现在$t$中的字符，然后求出他的$\pi$函数。由于$\#$的存在，很容易得到$\pi[i]$的值不会超过$n$。当$\pi[i]=n$时，代表此时$s[0...n-1]=cur[i-n+1...i]$。

pair<int, vector<int>> kmp(string s, string t)
{
    int n = s.length();
    int m = t.length();
    string cur = s + '#' + t;
    vector<int> pi = piFunction(cur);
    vector<int> show;
    int num = 0;
    for (int i = n; i < m + n + 1; i++)
    {
        if (pi[i] == n)
        {
            num++;
            show.push_back(i + 1 - n - n);
        }
    }
    return {num, show};
}