字符串快速匹配

  • 具体可以看这文章很详细 阮一峰

  • 匹配串 S, 和搜索串 P 中查找 P的位置。通常的暴力做法是每次移动指向 S 串的位置,如果不匹配再次移动。

    •   string s, p;
        int m, n;
        for (int i = 0; i < m; ++ i) {
        	bool flag = false;
        	
        	for (int j = 0; j < n; ++ j, ++ i) {
        		if (s[i] != p[j]) {
        			flag = true;
        			break;
        		}
        	}
        	if (!flag) printf("%d ", i);
        }
      
  • kmp 字符串匹配算法就是为了使得,通过 部分匹配表(next数组) 使得 i 不会向后回退。

next 数组

  • next[i] 表示的是,1~i 这个子字符串中,最长公共前后缀的长度。当我们第 i + 1 个数不匹配的时候,此时我们能够知道的1~i的字符串是匹配的。所以,我们可以移动匹配串,把前缀的位置移动到当前后缀的位置,然后继续比较下一个字符。

  • 求出next数组

    • 通过让字符串 p, 自匹配求出p[1~i] 每个字串的最长前后缀长度。
    •   int next[N];
        string p;
        int n;
        for (int i = 2, j = 0; i <= n; ++ i) {
        	/*
        		p[i] != p[j + 1] 则令j回退到 上一字符串公共前缀的最后一个字符上 再次进行匹配,若不匹配则继续回退,直到 j 为 0或满足p[i] === p[j + 1].
        		而p[1~j] 中必然存在前后缀最长匹配,所以只需要将前缀移动到后缀的位置,就可以继续匹配。
        	*/
        	while(j != 0 && p[i] != p[j+1]) j = ne[j]; 
        	if (p[i] == p[j + 1]) j ++;  // 匹配成功一个字符就 +1
        	next[i] = j;  // p[1~i] 最长 前后缀 j
        }
      
  • 通过next数组匹配

    • 操作和上面求next数组差不多
    •   for (int i = 1, j = 0; i <= m; ++ j) {
        	while(j != 0 && s[i] != p[j + 1]) j = ne[j];
        	if (s[i] == p[j + 1]) j ++;
        	if (j == n) {
        		// 匹配成功
        		printf("%d ", i - n);
        		// 再次匹配其他位置的字符串
        		j = ne[j];
        	}
        }
      

综合

  •   #include <iostream>
      #include <string>
      using namespace std;
    
      const int N = 100005;
      const int M = 1000005;
      int ne[N];
      char s[M], p[N];
    
      int main() {
      	int n, m;
      	cin >> n >> p + 1 >> m >> s + 1;
      
      	for (int i = 2, j = 0; i <= n; ++ i) {
          
          		while (j != 0 && p[i] != p[j + 1]) j = ne[j];
          			if (p[i] == p[j + 1]) j ++;
          			ne[i] = j;
      	}
      
      	for (int i = 1, j = 0; i <= m; ++ i) {
          	while (j != 0 && s[i] != p[j + 1]) j = ne[j];
          		if (s[i] == p[j + 1]) j ++;
          		if (j == n) {
              		j = ne[j];
              		cout << i - n << " ";
          		}
      	}
      	return 0;
      }
    

总结

  • 只要能明白next数组的含义就能理解kmp
  • next[i] = j , 表示 p[1~j] = p[i - j + 1], j 也是前缀的 尾部下标,也是最长匹配前后缀的长度。