字符串相关算法

1 字符串相关算法

1.1 回文串

string s;
int n=s.size();
//f[i][j]表示s[i:j]是否是回文串
vector<vector<int>> f(n,vector<int>(n,true));

s="abbab"
//从前向后处理，错误
//f[1][4]=(s[1]==s[4])&&f[2][3]
//f[1][4]需要用到f[2][3]，而f[2][3]还未处理
/*
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++)
            f[i][j]=(s[i]==s[j])&&f[i+1][j-1]; 
    }
*/
//从后向前处理
for(int i=n-1;i>=0;i--){
    for(int j=i+1;j<n;j++)
        f[i][j]=(s[i]==s[j])&&f[i+1][j-1];
}

1.2 LCP（最长公共前缀）

// f[i][j]表示s[i:]和s[j:]的最长公共前缀数量
vector<vector<int>> f(n+1,vector<int>(n+1,0));
for(int i=n-1;i>=0;i--){
    for(int j=n-1;j>i;j--){
        if(s[i]==s[j])
            f[i][j]=f[i+1][j+1]+1;
    }
}

2 字符串匹配算法

从文本中寻找模式串的匹配算法，蛮力算法及KMP算法

2.1 逐字符匹配

文本长度（T）：m

模式串长度（P）：n

下标从1开始，i为T的下标，j为P的下标

i 的下标范围为[1,m-n+1]，之后的长度小于n，肯定无法与模式串匹配

查找过程：T从某一下标i开始，P从1开始，T依次与P的相应位置匹配，如果不匹配，则回退到位置i+1，同时P的下标也回退到开始

2.2 KMP算法

串的前缀：除最后一个字符以外，字符串的所有头部子串 （ $aba前缀{a,ab}$）

串的后缀：除第一个字符以外，字符串的所有尾部子串（ $aba前缀{a,ba}$）

当文本串的第i个字符与模式串的第k个字符不匹配时，对于图中的情况，在第k个字符前存在相等的前缀和后缀时，可以将字符移动，用模式串的第t个字符与文本串的第i个字符继续进行比较，

因此，需要知道在Pattern第k个字符失配时，需要用哪个字符继续与Text第i个字符比较

2.2.1 求next(j)：

第j个字符前，使前缀串=后缀串的最大值为k

则next[j]=k+1

$$
\begin{equation}
next[j]=

\begin{cases}
0& \text{j=1}\
max{k,1<k<j且’p_1…p_k’=‘p_{j-k+1}…p_{j-1}’}& \text{此集合不空时}\
1& \text{其他情况}

\end{cases}

\end{equation}
$$

规定next[1]为0，当第1个字符就不匹配时，用第0个字符用Text[i]比较，相当于在Pattern前添加一个空字符

P[1]!=T[j]时，用P[0]与T[j]比较

即P[1]与T[j+1]比较

### 求next程序

void get_Next(string &P, vector<int> &next) {
    next[1] = 0;
    int i = 1, j = 0;
    while (i < P.size()) {
        if (j == 0 || P[j - 1] == P[i - 1]) {
            i++;
            j++;
            next[i] = j;
        } else
            j = next[j];
    }
}

j处于Patter前部，当next[i]=next[j]时

说明i+1前的前缀串=后缀串的长度为j，

则next[i+1]=j+1

next(j)产生过程：

j	1	2	3	4	5	6	7	8
模式串	a	b	a	a	b	c	a	c
next[j]	0	1	1	2	2	3	1	2

j=0	i=1		=>	j=1	i=2	next[2]=1
		p[1] != p[2]	=>			j=next[1]=0
j=0	i=2		=>	j=1	i=3	next[3]=1
		p[1] = p[3]	=>	j=2	i=4	next[4]=2
		p[2] !=p[4]	=>			j=next[2]=1
		p[1] = p[4]	=>	j=2	i=5	next[5]=2
		p[2] = p[5]	=>	j=3	i=6	next[6]=3

2.2.2 KMP模板

(99+ 封私信 / 84 条消息) 如何更好地理解和掌握 KMP 算法? - 知乎 (zhihu.com)

// 返回s中t出现多少次
  int KMP(string s, string t) {
      vector<int> next = getNext(t);
      // 匹配t数目，当前匹配的字符数
      int match = 0, count = 0;
      //第count个字符没有匹配上，则取可以匹配的最长前缀长度k，其中[0,k-1]可以匹配上
      for (int i = 0; i < s.size(); i++) {
          while (count && t[count] != s[i])
              count = next[count - 1];

          if (t[count] == s[i])
              count++;
          if (count == t.size()) {
              match++;
              count = next[count - 1];
          }
      }
      return match;
  }
  //next[i]前后缀相等的最大长度
  vector<int> getNext(string pattern) {
      int n = pattern.size();
      vector<int> next(n);
      int count = 0;
      for (int i = 1; i < n; i++) {
          while (count && pattern[count] != pattern[i])
              count = next[count - 1];
          if (pattern[count] == pattern[i])
              ++count;
          next[i] = count;
      }
      return next;
  }

2.3 Horspool算法

void ShiftTable(string &P, unordered_map<char, int> &table) {
    //范围不到最后一个字符
    for (int i = 0; i < P.size() - 1; i++) {
        table[P[i]] = P.size() - i - 1;
        // cout << P[i] << " " << table[P[i]] << endl;
    }
}
int Horspool(string &T, string &P) {
    unordered_map<char, int> table;
    ShiftTable(P, table);

    int n = T.size(), m = P.size();
    int i = m - 1;
    while (i < n) {
        int k = 0; //已经匹配的字符数
        while (P[m - 1 - k] == T[i - k] && k < m) {
            k++;
        }
        if (k == m)
            return i - m + 1;

        // T[i]是与模式不匹配的字符
        //如果其不在模式中时，则模式与其下一个位置匹配
        //如果在模式中时，移动模式使最右侧的该字符与T[i]对齐
        if (table.find(T[i]) == table.end())
            i = i + m;
        else
            i = i + table[T[i]];
        // cout << i << endl;
    }
    return -1;
}

2.4 Boyer-Moore算法

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
/*
    字符串匹配算法
    T:text文本
    P:pattern模式串
*/

//返回下标从0开始计数的位置
int BruteForceStringMatch(string t, string p) {
    int n = t.size(), m = p.size();
    for (int i = 0; i <= n - m; i++) {
        int k = 0;
        while (k < m && t[k + i] == p[k])
            k++;
        if (k == m)
            return i;
    }
    return -1;
}

/*
    返回从pos位置开始第一个与P匹配的首字符位置
    这里j为1表示字符串第一个字符
    j=0表示P的第一个字母与T的当前字母不匹配
    查找位置pos为下标序，从0开始
*/
void get_Next(string &P, vector<int> &next);
int KMP(string T, string P, int pos) {
    int n = T.size(), m = P.size();
    vector<int> next(m + 1);
    get_Next(P, next);
    int i = pos, j = 0;
    while (i <= n && j <= m) {
        if (j == 0 || T[i - 1] == P[j - 1]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j > m)
        return i - j;
    return -1;
}
void get_Next(string &P, vector<int> &next) {
    next[1] = 0;
    int i = 1, j = 0;
    while (i < P.size()) {
        if (j == 0 || P[j - 1] == P[i - 1]) {
            i++;
            j++;
            next[i] = j;
        } else
            j = next[j];
    }
}

void ShiftTable(string &P, unordered_map<char, int> &table) {
    //范围不到最后一个字符
    for (int i = 0; i < P.size() - 1; i++) {
        table[P[i]] = P.size() - i - 1;
        // cout << P[i] << " " << table[P[i]] << endl;
    }
}
int Horspool(string &T, string &P) {
    unordered_map<char, int> table;
    ShiftTable(P, table);

    int n = T.size(), m = P.size();
    int i = m - 1;
    while (i < n) {
        int k = 0; //已经匹配的字符数
        while (P[m - 1 - k] == T[i - k] && k < m) {
            k++;
        }
        if (k == m)
            return i - m + 1;

        // T[i]是与模式不匹配的字符
        //如果其不在模式中时，则模式与其下一个位置匹配
        //如果在模式中时，移动模式使最右侧的该字符与T[i]对齐
        if (table.find(T[i]) == table.end())
            i = i + m;
        else
            i = i + table[T[i]];
        // cout << i << endl;
    }
    return -1;
}
int main() {
    string text = "acabaabaabcacaabc", pattern = "abaabc";
    cout << BruteForceStringMatch(text, pattern) << endl;
    cout << KMP(text, pattern, 3) << endl;
    string P = "BARBER", T = "JIM_SAW_ME_IN_A_BARBERSHOP";
    cout << Horspool(T, P) << endl;
    getchar();
}

2.5 题目

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

class Solution {
public:
    int strStr(string haystack, string needle) {
        return KMP(haystack,needle);
    }
    int KMP(string &s,string &p){
        int m=s.size(),n=p.size();
        vector<int> next(n);
        getNext(next,p);
        int i=0,j=0;
        while(i<m&&j<n){
            if(j==-1||s[i]==p[j]){
                i++;
                j++;
            }else
                j=next[j];
        }
        return j==n?i-j:-1;
    }

    void getNext(vector<int>&next,string &p){
        next[0]=-1;
        int i=-1,j=0;
        while(j<p.size()-1){
            if(i==-1||p[i]==p[j]){
                i++;
                j++;
                next[j]=i;
            }else
                i=next[i];
        }
    }
};

2.5.2 模式串在主串中有多少个完全匹配的主串？

#include <iostream>
#include <vector>
#include <string>
using namespace std;

void Get_Next(string P, vector<int> &next)
{
    next[1] = 0;
    int j = 0, i = 1;
    int len = P.size();
    while (i < len)
    {
        if (j == 0 || P[j - 1] == P[i - 1])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
            j = next[j];
    }
}
int KMP(string T, string P)
{
    int m = T.size(), n = P.size();
    vector<int> next(n + 1);
    Get_Next(P, next);

    int count = 0;
    int i = 0, j = 0;
    while (i <= m - n + 1)
    {
        if (j == 0 || T[i - 1] == P[j - 1])
        {
            i++;
            j++;
        }
        else
            j = next[j];

        if (j >= n)
        {
            i = i - j + 2;
            j = 0;
            count++;
        }
    }
    return count;
}
int main()
{
    string text = "aaabcdaa", pattern = "aa";
    cout << KMP(text, pattern) << endl;
    return 0;
}