JavaScriptAlgorithms/Classical algorithm problem/Boyer-Moore.html at master · biaodigit/JavaScriptAlgorithms · GitHub

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>BM算法(坏字符匹配)</title>
</head>
<body>
<script>
    function BoyerMoore(text, pattern) {
        let tLen = text.length,
            pLen = pattern.length,
            badSuffix = {},
            goodSuffix = Array(pLen),
            suffixArr = Array(pLen);
        let match = function () {
            computeBadSuffix();
            computeGoodSuffix();

            console.log(badSuffix)
            console.log(goodSuffix)
            let i = pLen - 1,
                j = pLen - 1,
                lastIndex;
            while (i < tLen) {
                if (pattern.charAt(j) === text.charAt(i)) {
                    if (j === 0) {
                        console.log(i)
                        return;
                    }
                    i--;
                    j--
                } else {
                    lastIndex = badSuffix[text.charAt(i)] >= 0 ? badSuffix[text.charAt(i)] : -1;
                    i += pLen - 1 - j + Math.max(j - lastIndex, goodSuffix[j]);
                    j = pLen - 1;
                }
            }
            console.log(-1)
        };


        let computeBadSuffix = function () {
            for (let j = 0; j < pLen - 1; j++) {
                badSuffix[pattern.charAt(j)] = j
            }
        };

        let computeGoodSuffix = function () {
            computeSuffixLength();

            //case 3 模式串中没有字串对应好后缀
            for (let i = 0; i < pLen; i++) {
                goodSuffix[i] = pLen;
            }

            //case2 模式串开头存在部分好后缀
            let j = 0;
            for (let i = 0; i < pLen; i++) {
                if (suffixArr[i] === i + 1) {
                    while (j <= pLen - 1 - i - 1) {
                        if (goodSuffix[j] === pLen) {
                            goodSuffix[j] = pLen - 1 - i;
                        }
                        j++
                    }
                }
            }

            //case1 模式串中有子串与好后缀完全匹配
            for (let i = 0; i < pattern.length - 1; i++) {
                goodSuffix[pLen - 1 - suffixArr[i]] = pLen - 1 - i
            }
        };

        // 计算匹配字符串的公共前后缀个数
        let computeSuffixLength = function () {
            suffixArr[suffixArr.length - 1] = suffixArr.length;
            let q;
            for (let i = suffixArr.length - 2; i >= 0; i--) {
                q = i;
                while (q >= 0 && pattern.charAt(q) === pattern.charAt(pLen - 1 - i + q)) {
                    q--
                }
                suffixArr[i] = i - q
            }
        };
        match()

    }

    BoyerMoore("here is a simple example", "example")
</script>
</body>
</html>