7-KMP

算法思想

1. 设计出暴力算法
2. 改进算法
   1. 使用 next 数组，跳过不可能成功的字符串比较

算法细节

next 数组

对于模式串 p 来说，next[ i ] = j ( i > 0, j < i ) 表示子串 p[ 0 .. i - 1 ] 的最长的公共前后缀的长度为 j。 例如，next[ i ] = j 表示 p[ 0 .. j - 1 ] = p[ i - j .. i - 1 ]，即前 j 个字符与后 j 个字符相同。 若 j == i ，则表示公共前后缀为子串 p [ 0 .. i - 1 ] ，这对于解决问题没有帮助。

如何求解 next 数组

1. 设计出暴力算法
2. 改进算法
   1. 跳过不可能成功的前后缀比较

求解 next 数组的改进算法

暴力算法的问题是什么

• 当前后缀不匹配时，需要减短前后缀的长度，重新检查是否匹配
• 暴力算法需要遍历并比较所有的前后缀
• 存在不可能成功的字符串比较

改进算法的优势是什么

• 可以跳过**不可能成功的字符串比较
• 规律为串 A 和串 B 不匹配时，让 now 指针指向 next[ now - 1 ] ，可以跳过不可能成功的字符串比较

字符串比较的改进算法

• 与求解 next 数组的改进算法，完全相同

算法模板

求解 next 数组的暴力算法

static int[] computeNext(char[] p)
{
	int n = p.length;   
	int[] ne = new int[n];
	
	for(int i = 2; i < n; i ++ )
	{
		for(int j = i - 2; j > 0; j -- )
		{
			var head = new String(p, 0, j);
			var end = new String(p, i - j, i - 1);
			if(head.equals(end))
			{
				ne[i] = j;
				break;
			}
		}
	}
	
	return ne;
}

朴素算法

import java.util.*;

public class Main {
    static int N = 1000010;
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        var p = in.next().toCharArray();
        int m = in.nextInt();
        var s = in.next().toCharArray();
        
        for(int i = 0; i < m - (n - 1); i ++ )
        {
            boolean isMatch = true;
            for(int j = 0; j < n; j ++ )
            {
                if(p[j] != s[i + j])
                {
                    isMatch = false;
                }
            }
            if(isMatch)
            {
                System.out.print(i + " ");
            }
        }
    }
}

KMP算法

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

public class Main {
    static int N = 1000010;
    static char[] p = new char[N];
    static char[] s = new char[N];
    // ne[i] = j 代表模式串 p 中的子串 p[1 .. i] 中最大的公共前后缀的长度为 j
    // 即，p[1 .. j + 1] == p[i - j .. i]
    static int[] ne = new int[N];
    
    public static void main(String[] args) throws IOException {
        var br = new BufferedReader(new InputStreamReader(System.in));
        var bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        String P = br.readLine();
        int m = Integer.parseInt(br.readLine());
        String S = br.readLine();
        // 下标从1开始        
        for(int i = 1; i <= n; i ++ ) p[i] = P.charAt(i - 1);
        for(int j = 1; j <= m; j ++ ) s[j] = S.charAt(j - 1);
        
        for(int i = 2, j = 0; i <= n; i ++ )
        {
			// j 即代表指针，又代表最长公共前后缀的长度
            // 比较子串 A 的第 j + 1 位与子串 B 的第 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)
            {
                bw.write((i - n) + " ");
                j = ne[j];
            }
        }
        bw.flush();
    }
}

参考资料

• KMP算法教程