青菜猫(孙宇博客),青菜猫(孙宇博客),青菜猫(孙宇博客)http://www.javasdc.cn/
posts - 29,  comments - 63,  trackbacks - 0


     BF(Brute Force)算法核心思想是:首先S[1]和T[1]比较,若相等,则再比较S[2]和T[2],一直到T[M]为止;若S[1]和T[1]不等,则T向 右移动一个字符的位置,再依次进行比较。如果存在k,1≤k≤N,且S[k+1…k+M]=T[1…M],则匹配成功;否则失败。该算法最坏情况下要进行 M*(N-M+1)次比较,时间复杂度为O(M*N)
     比如: String a ="123456789" String b= "23"
   其实就是循环 a一个一个字符匹配,开始a[0]和b[0]匹配,没有找到,直接不用找b[1],直接用a[1]和b[0]匹配发现已经 找到,然后继续用
a[2]和b[1]匹配发现已经 找到。前且是b字符串末尾。说明已经完全找到。返回结果
  JAVA代码实现
/**
     * 匹配字符串,判断 b字符串在a出现的起始位置,没有找到返回(-1)
     * @param a
     * @param b
     * @return
     */
    public static int indexOf(String a,String b){
        char[] as = a.toCharArray();
        char[] bs = b.toCharArray();
        int begin = 0;
        for(int i = 0 ; i <as.length; i++){
            int k = nextStr(as[i], bs,begin);
            //说明已经找到
            if( k == begin ){
                return i-begin;
            }
            //说明找到一个字符,需要继续找
            else if( k >= 0 ){
                begin = k;
            }else{
            //没有找到继续找    
            begin = 0;
            }
        }
        return -1;
    }
    
    
    /**
     * 匹配字符串,找到字符串位置
     * @param c
     * @param cs
     * @param begin
     * @return
     */
    public static int nextStr(char c,char[] cs,int begin){
        //如果字符匹配和已经到了字符尾部青示已经全部匹配
        if(cs[begin] == c && begin == (cs.length-1) ){
            return begin;
        //如果字符匹配但没有到尾部需要继续下移
        }else if(cs[begin] == c){
            return begin+1;
        }
        //完全没有匹配
        else{
            return -1;
        }
    }

 然后在main里面调用indexOf方法看到结果
posted on 2013-05-21 16:11 青菜猫(孙宇) 阅读(978) 评论(0)  编辑  收藏 所属分类: 其它

只有注册用户登录后才能发表评论。


网站导航:
 
<2013年5月>
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

青菜猫(孙宇)结交天下朋友,在网上吸取知识..

常用链接

留言簿(16)

随笔分类

随笔档案

文章分类

搜索

  •  

最新评论

阅读排行榜

评论排行榜

青菜猫(孙宇博客),青菜猫(孙宇博客),青菜猫(孙宇博客)http://www.javasdc.cn/