Java字符串匹配算法

定义

串(string)是由零个或多个字符组成的有限序列又名叫字符串。

• 一般地，由n个字符串构成的串记作: S=“a₀a₁…a_n-1”(n≥0),其中a_i（1≤i≤n）
• n是个有限的数值
• 串一般记为S是串的名称,用引号括起来的字符序列是串的值
• 可以是字母,数字或其他字符,i就是该字符在串中的位置,串中的字符数目n称为串的长度

子串

在对字符串S做处理时,经常需要取出其中某一连续的片段,称为S的子串(substring)

• 具体地，由串S中起始于位置i的连续k个字符组成的子串记作substr(S,i,k) = “a_ia_i+1…a_i+k-1”,0≤i (n,0≤k)

• 前缀 prefix(S,k) = substr(S,0,k);
• 后缀 suffix(S,k) = substr(S,n-k,k)
• 空格串：只包含空格的串。

BF字符串暴力解法

基本思想

1. 从主串的第一个字符起与子串的第一个字符进行比较,若相等,则继续对字符串进行后续的比较
2. 若不相等，则从主串第二个字符起与子串的第一个字符重新比较，以此类推，直到子串中每个字符依次和主串中的一个连续的字符序列相等为止，此时称为匹配成功。
3. 如果不能在主串中找到与子串相同的字符序列，则匹配失败。

需要进行回溯操作,否则会错过相等的部分

 /**
     *
     * @param parent 主串
     * @param sub 子串
     */
    public static void bruteForce(String parent,String sub){
        //成功匹配的位置
        int index = -1;
        //主串的长度
        int pLen = parent.length();
        //子串的长度
        int sLen = sub.length();

        if (pLen<sLen){
            System.out.println("Error.The main string is greater than the sub string length.");
            return;
        }

        int i = 0;
        int j = 0;
        while (i<pLen&&j<sLen){
            // 判断对应位置的字符是否相等
            if (parent.charAt(i)==sub.charAt(j)){
               //若相等.主串子串继续比较
               i++;
               j++;
            }else{
                //主串回溯到上一次开始匹配的下一个字符
                i = i- j+1;
                j = 0;
            }
        }
        //匹配成功
        if (j >= sLen) {
            index = i - j;
            System.out.println("Successful match,index is:" + index);
        } else {// 匹配失败
            System.out.println("Match failed.");
        }
    }

KMP算法

其核心思想是主串不回溯,模式串尽量多向右移动

首先构造next表(next表里存放的是字符串真后缀与真前缀相同的子字符串最大长度):

以ABCDABD为例说明构建next表

P = ABCDABD
j = 0, prefix(P, 0) = φ
next[0] = -1;//规定如此

P = ABCDABD
j = 1, prefix(P, 1) = A
真前缀: φ
真后缀: φ
next[1] = 0;

P = ABCDABD
j = 2, prefix(P, 2) = AB
真前缀: A
真后缀: B
next[2] = 0;

P = ABCDABD
j = 3, prefix(P, 3) = ABC
真前缀: A,AB
真后缀: BC,C
next[3] = 0;

P = ABCDABD
j = 4, prefix(P, 4) = ABCD
真前缀: A,AB,ABC
真后缀: BCD,CD,D
next[4] = 0;

P = ABCDABD
j = 5, prefix(P, 5) = ABCDA
真前缀: A,AB,ABC,ABCD
真后缀: BCDA,CDA,DA,A
next[5] = 1;

P = ABCDABD
j = 6, prefix(P, 6) = ABCDAB
真前缀: A,AB,ABC,ABCD,ABCDA
真后缀: BCDAB,CDAB,DAB,AB,B
next[6] = 2;

得出next表为:
[-1, 0, 0, 0, 0, 1, 2]

代码实现

package string;

public class KMP {
    //构建next表
    public static int[] buildNext(String sub){
        //构建next表就是查找真前缀 == 真后缀的最大长度，以获取模式串尽量多地往右移动
        int[] next = new int[sub.length()];
        //主串位置
        int j = 0;
        //子串位置
        int t = next[0] = -1;

        while (j<sub.length()-1){
            if (t<0||sub.charAt(j)==sub.charAt(t)){
                j++;
                t++;
                next[j] = t;
            }else {
                t = next[t];
            }
        }
        return next;
    }

    public static void kmp(String parent,String sub){
        int[] next = buildNext(sub);
        //成功匹配的位置
        int index = -1;
        //主串的长度
        int pLen = parent.length();
        //子串的长度
        int sLen = sub.length();

        if (pLen<sLen){
            System.out.println("Error.The main string is greater than the sub string length.");
            return;
        }

        int i = 0;
        int j = 0;
        while (i<pLen&&j<sLen){
            // 判断对应位置的字符是否相等
            if (j==-1||parent.charAt(i)==sub.charAt(j)){
                //若相等.主串子串继续比较
                i++;
                j++;
            }else{
                //i不变,j=next[j]
                j = next[j];
            }
        }
        //匹配成功
        if (j >= sLen) {
            index = i - j;
            System.out.println("Successful match,index is:" + index);
        } else {// 匹配失败
            System.out.println("Match failed.");
        }
    }
}