BM算法--串匹配

浏览数：31 / 时间：2015年06月08日

BM(Boyer-Moore)算法，后缀匹配,是指模式串的比较从右到左,模式串的移动也是从左到右的匹配过程，一般情况比KMP算法要快。时间复杂度O(m/n)

技术分享

C++描述（教师版）

int BM(char S[],char T[], int n, int m)
{
//主串长度为n，模式串长度为m，主串和模式串的数组下标从1开始
      int i=m;
      int j;
      while(i<=n){
            j=m;
            while(j>0&&S[i]==T[j]){
	   j--;
	   i--;
            }
            if(j==0) return i+1;
            else {
	    i=i+dist(S[i],T,m);  
	    cout<<"重新从主串的"<<i<<"处向前匹配"<<endl;
            }
      }
      return

　我的javascript版实现

<!DOCTYPE html>
<html>
<head lang="en">
    <meta charset="UTF-8">
    <title>BM算法</title>
    <script type="text/javascript" src="jquery.min.js"></script>
    <script type="text/javascript">
        //T:子串，S:主串,SI:主串起始下标,TJ:子串起始下标
        function BM(S, T, SI, TJ) {
            while ( TJ >=0&&SI<S.length) {
                if (S[SI] == T[TJ]) {

                    if (TJ==0) {
//返回开始的位置，自然记数。
                        return SI+1;
                    }

                    SI--;
                    TJ--;

                } else {
                    SI = SI + dist(T, S[SI]);
                    TJ = T.length - 1;
                }
            }
//查找不到时返回-1
             return -1;



        }


        function dist(array, target) {
            for (var i = 0; i < array.length; i++) {
                if (array[i] == target) {
                    if (i == array.length - 1) {
                        return array.length;
                    }

                    return array.length - i -1;
                }


            }


            return array.length;


        }


    </script>
</head>
<body>

<input type="text" id="S" placeholder="要查找的字符串"/><br/>
<input type="text" id="T" placeholder="关键字符串"/><br/>
<input type="button"  value="确认" onclick="demo();"/>
<script type="text/javascript">
    function demo() {
        var S = $(‘#S‘).val();
        var T = $(‘#T‘).val();
        alert(BM(S, T, T.length - 1, T.length - 1));

    }
</script>


</body>
</html>