首页 > 其他 > 详细

Boyer-Moore: Implement strStr() --- find a needle in a haystack

时间:2015-06-02 06:46:45      阅读:211      评论:0      收藏:0      [点我收藏+]

https://www.youtube.com/watch?v=izMKq3epJ-Q

Boyer-Moore algrt 关于skip的部分很重要

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

 

public class Solution {
    public int strStr(String haystack, String needle) {
        int[] hs = new int[256];
        int h=haystack.length();
        int n = needle.length();
        for(int i=0;i<256;i++){
            hs[i] = -1;
        }
        for(int i=0;i<n;i++){
            hs[needle.charAt(i)] = i;
        }
        int sk = 0;
        for(int i=0;i<h-n+1;i+=sk){
            sk = 0;
            for(int j=n-1;j>=0;j--){
                if(haystack.charAt(i+j)!=needle.charAt(j)){
                    sk = Math.max(1,j-hs[haystack.charAt(i+j)]);
                    break;
                }
            }
            if(sk==0) return i;
        }
        return -1;
    }
}

 

Boyer-Moore: Implement strStr() --- find a needle in a haystack

原文:http://www.cnblogs.com/jiajiaxingxing/p/4545372.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!