Java-串(BF和KMP算法)_基于bfk和mp算法编写一个java程序,给定两个字符串s和t,求串t在串s中不重叠出现的

BF

一种简单的模式匹配算法，目的是寻找模式串p是否在目标串s中有出现。

思想：先从第一个字符开始匹配，如果p[j]==s[i]，那么继续向下比较，一旦不相等，即回溯到目标串的下一个字符，重复工作。

成功条件：当循环结束时，判断j的值与模式串p的长度是否相等，如果相等，说明匹配成功到了模式p的最后一个字符。

返回值：返回模式串在目标串中出现的位置。

/**
 * 字符串模式匹配的 Brute-Force算法（暴力法）
 * @author huanmin
 *
 */

public class StrMatchBF {

    /**
     * 匹配字符串
     * @param iniStr 原始字符串
     * @param patternStr 模式字符串
     * @return 如果模式字符串在原始字符串中存在，返回模式字符串在原始字符串中第一次出现的索引。
     */
    public int indexOfStr(String iniStr, String patternStr) {
        if(iniStr == null || iniStr.length() <= 0 ||
                patternStr == null || patternStr.length() <=0) {
            return -1;
        }

        int iniLength = iniStr.length();
        int patternLength = patternStr.length();
        int i = 0, j = 0; //两个字符的起始下标
        while(i < iniLength && j < patternLength) {
            //比较两个字符串的同位置的元素
            if(iniStr.charAt(i) == patternStr.charAt(j)) {
                i++;
                j++;
            } else {
                // 失配，回退 下一个索引位置
                i = i - j + 1;
                     //匹配字符串从0开始
                j = 0;
            }
        }
        //检测是否完全匹配完成
        if(j == patternLength) {
            //计算下标(模式字符串在原字符串的开始位置)
            return i - patternLength;
        } else {
            return -1;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

KMP

KMP算法的好处就是不用回溯,还可以避免不必要的匹配！而是以一种滑动的方式匹配模式串。此算法不细讲,因为就算写了原理也看不懂.还不如你自己研究比较好

KMP运行流程:
先看一下 KMP 算法运行流程（假设主串：ababcabcacbab，模式串：abcac）

第一次匹配:

匹配失败，i 指针不动，j = 1（字符‘c’的next值）;

第二次匹配:

相等，继续，直到：

匹配失败，i 不动，j = 2 （ j 指向的字符 ‘c’ 的 next 值）;

第三次匹配：

相等，i 和 j 后移，最终匹配成功。

注意：对于上边的KMP算法中的next数组，不是最精简的，还能够简化。从而减少匹配的次数 (简单的来说就是跳过重复匹配)

总结:KMP 算法，之因此比 BF 算法快的根本缘由在于：KMP 算法其实也和 BF 算法同样，都是从主串开头开始匹配，可是在匹配过程当中，KMP算法记录了一些必要的信息。根据这些信息，在后续的匹配过程当中，跳过了一些无心义的匹配过程。

/**
 * 字符串匹配的KMP算法 (最快匹配法)
 *
 * @author huanmin
 */
public class StrMatchKMP {

    public static int indexOfStrKMP(String iniStr, String patternStr) {
        if (iniStr == null || iniStr.length() <= 0 ||
                patternStr == null || patternStr.length() <= 0) {
            return -1;
        }

        // 得到模式串的next数组
        int[] nextArr = getNextArray(patternStr);
        int iniLength = iniStr.length();
        int patternLength = patternStr.length();
        int i = 0;  // 原始串索引
        int j = 0;  // 模式串索引
        while (i < iniLength && j < patternLength) {
            if (j == -1 || iniStr.charAt(i) == patternStr.charAt(j)) {
                i++;
                j++;
            } else {
                //匹配失败,取下一个匹配位置(i不动,调整j的匹配位置)
                j = nextArr[j];
            }
        }
        if (j == patternLength) {
            return i - patternLength;
        } else {
            return -1;
        }
    }

    /**
     * 获取模式字符串的next数组
     *
     * @param str
     * @return
     */
    private static int[] getNextArray(String str) {
        if (str == null || str.length() <= 0) {
            return null;
        }
        int length = str.length();
        int[] nextArr = new int[length];
        nextArr[0] = -1;//跳过第一个

        //j>k  永远k比j少1
        int j = 0;
        int k = -1;
        while (j < length - 1) {
            //等于-1  或者 j=k
            if (k == -1 || str.charAt(j) == str.charAt(k)) {
                // 匹配，移动
                j++;
                k++;
                if (str.charAt(j) == str.charAt(k)) {
                    //判断移动之后,的字符串是否相等,如果相等那么j从上一个k位置进行匹配(k<j)
                    nextArr[j] = nextArr[k];
                } else {
                    //如果不相等那么j,从k的位置开始匹配
                    nextArr[j] = k;
                }
            } else {
                //算出最大长度
                k = nextArr[k];
            }
        }
        return nextArr;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

点赞 -收藏-关注-便于以后复习和收到最新内容 有其他问题在评论区讨论-或者私信我-收到会在第一时间回复 如有侵权，请私信联系我 感谢,配合,希望我的努力对你有帮助^_^