kmp算法

kmp是一种高效存储字符串匹配的算法

关键：在主串中找模板串的位置

遇到两个字符不匹配的情况时，希望可以多跳几个字符，减少比较次数。KMP算法的思想是：在模式串和主串匹配过程中，当遇到不匹配的字符时，对于主串和模式串中已对比过相同的前缀字符串，找到长度最长的相等前缀串，从而将模式串一次性滑动多位，并省略一些比较过程。

模板

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && 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 <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}

题目

AcWing 831

831 Kmp字符串

题目描述：

给定一个模式串S，以及一个模板串P，所有字符串中只包含大小写英文字母以及阿拉伯数字。

模板串P在模式串S中多次作为子串出现。

求出模板串P在模式串S中所有出现的位置的起始下标。

题解：

做法一：暴力解

for (int i = 1; i <= n; i ++ )
{
    bool flag = true;
    for (int j = 1; j <= m; j ++ )
    {
        if (s[i + j - 1] != p[j])
        {
            flag=false;
            break;
        }
    }
}

做法二：kmp

kmp解法：

kmp的核心是next数组，next数组就是每次不匹配后跳转的值
为什么可以使用kmp呢？看图
如何找到kmp中的next？

next的特征是？

next[i] 的含义：以i为终点的后缀，和从1开始的前缀相等，最长

终点是i，当不能匹配时，得到next[i]=j,j是最长的前缀匹配，跳转j值
一般母串的i-1 匹配j， i匹配j+1，错一位

next看图

看 abababc

next[1] = 0, next[2]=0,next[3]=1,next[4]=2

代码：

import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	static final int N = 10010; //模板串
	static final int M = 100010; //匹配串  
	static char[] p = new char[N]; //模板串
	static char[] s = new char[M]; //被匹配的字符串  母串
	static int[] next = new int[N]; //next数组
    
 	public static void main(String[] args) throws IOException {
    	//输入
        
        //都从一开始
        int n = Integer.parseInt(br.readLine());
		String pStr = br.readLine();
		for(int i=1;i<=n;i++){
			p[i] = pStr.charAt(i-1); //模板
		}
		
		int m = Integer.parseInt(br.readLine());
		String sStr = br.readLine();
		for(int i=1;i<=m;i++){
			s[i] = sStr.charAt(i-1); //母串
		}
        
        //next数组初始化过程
        for(int i = 2,j=0;i<=n;i++){
            while(j!=0&&p[i]!=p[j+1]){
				j=next[j];
			}
            if(p[i]==p[j+1]){
                j++;
            }
            
            next[i]=j;
        }
        
        
        
        //匹配过程
        //i是指向s将要匹配的位置
        //j是指向模板串已经匹配成功的位置
        // i-1 j， i j+1
        //总之 i 和 j+1 错一位
        //s[i]母串  p[j]模板
        for(int i=1,j=0;i<=m;i++){
            //j没有退回起点，匹配失败
            while(j!=0&&s[i]!=p[j+1]){
                j = next[j];
            }
            //跳转了之后再继续向下匹配
            if(s[i]==p[j+1]){
                j++;
            }
            
            if(j==n){
                bw.write(i-n+" "); //输出起始位置下标
                j = next[j];
            }
        }
        
        bw.flush();
		bw.close();
		br.close();
    }
    
}

总结下：kmp算法：

一个字符串再另一个母串中出现的次数
next数组只和字串有关，与母串无关
next求法与匹配方法类似
next[i] i从1开始
s[i]和p[j] i-1~j, i~j+1

kmp next数组的初始化过程
for(int i = 2,j=0;i<=n;i++){
    while(j!=0&&p[i]!=p[j+1]){
        j=next[j];
    }	
    if(p[i]==p[j+1]){
        j++;
    }

    next[i]=j;
}

kmp的匹配过程
for(int i=1,j=0;i<=m;i++){
    while(j!=0&&s[i]!=p[j+1]){
        j=next[j];
    }
    if(s[i]!=p[j+1]){
        j++;
    }
    if(j==n){
        //匹配成功了
        //...
        j=next[j];
    }
}