常用经典算法

1. KMP算法
- 1.1. 核心思想
  - 1.1.1. lps[i]存放什么？
  - 1.1.2. 如何构建lps[]数组？
- 1.2. Java实现

1. KMP算法

全称Knuth-Morris-Pratt Algorithm，是一种高效的字符串匹配算法。

1.1. 核心思想

利用待查找的字符串pattern[0..m-1]构造一个辅助数组lps[0..m-1]，这是KMP算法实现高效匹配的核心。

1.1.1. lps[i]存放什么？

先定义下面一些概念：
对于字符串”ABC”，它的：

prefixes: “”,”A”,”AB”,”ABC”
proper prefixes: “”,”A”,”AB”（不包括字符串本身）
suffixes: “”,”C”,”BC”,”ABC” 了解了上面的一些概念，现在可以说lps[i]的意义了。

对于字符串pattern[0..i]： lps[i]=the length of longest proper preffix of pattern[0..i] which is a suffix of pattern[0..i]。（LPS[i] = MAXIMUM(j) such that string[0 to j-1] == string[i-j+1 to i]）

概念有时很难理解，现在看一些例子。

对于pattern[]: “AAAA”
lps[]: [0,1,2,3]

对于pattern[]: “ABCDE”
lps[]: [0,0,0,0,0]

对于pattern[]: “AABAACAABAA”
lps[]: [0,1,0,1,2,0,1,2,3,4,5]

1.1.2. 如何构建lps[]数组？

参考：https://iq.opengenus.org/prefix-table-lps/

1.2. Java实现

package com.hb.nowcoder.string;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class KMP {
    public static void main(String[] args) {
        KMP demo= new KMP();
        
        /*
         * int[] lps = demo.getLPS("ACDAC"); System.out.println(Arrays.toString(lps));
         */
        
        String text="ABCDABCEDJSABC";
        String pattern="";
        
        int[] result = demo.search(text, pattern);
        System.out.println("共搜索到"+result.length+"处");
        System.out.println("结果："+Arrays.toString(result));
        
    }
    
    /**
     * KMP算法搜索一个文本在另一个文本中出现的所有位置
     * @param t 文本字符串
     * @param p 模板字符串
     * @return p在t中出现的位置数组
     */
    public int[] search(String t,String p) {
        
        
        List<Integer> idxes = new ArrayList<>();
        int N = t.length();
        int M = p.length();
        if(M==0) {
            return new int[]{};
        }
        int i=0,j=0;
        //计算lps数组
        int[] lps = getLPS(p);
        
        while(i<t.length()) {
            if(t.charAt(i)==p.charAt(j)) {
                i++;
                j++;
                //已经找到匹配处
                if(j==M) {
                    idxes.add(i-j);
                    j=lps[j-1];
                }
            }else {
                //text[i]和pattern[j]不匹配
                if(j==0) {	
                    //j为0都不匹配,那么i需要后移
                    i++;
                }else {
                    //j>0，回溯（跳过lps[j-1]个字符的匹配）
                    j=lps[j-1];
                }
            }
        }
        return idxes.stream().mapToInt(Integer::intValue).toArray();
    }
    
    /**
     * 生成模板字符串p的lps数组
     * @param pattern
     * @return
     */
    private int[] getLPS(String pattern) {
    
        int i=0,j=1;
        int[] lps=new int[pattern.length()];
//		lps[0]总是0
        lps[0]=0;
        while(j<pattern.length()) {
            if(pattern.charAt(i)==pattern.charAt(j)) {
                lps[j]=i+1;
                i++;
                j++;
            }else {
                /*Pi和Pj不匹配*/
                if(i==0) {
                    lps[j]=0;
                    j++;
                }else {
                    i=lps[i-1];
                }
            }
            
        }
        return lps;
        
    }
}