基本字符串匹配算法

//之前温习的字符串匹配KMP算法
    static int matchCount(String str, String sub)
    {
        char[] chStr = str.toCharArray();
        char[] chSub = sub.toCharArray();
        int count = 0;
        for(int i = 0; i < chStr.length; i++)
        {
            int j = 0;
            for(int k = i; j < chSub.length && k<chStr.length; j++,k++)
            {
                if(chStr[k] == chSub[j])
                {
                    continue;
                }
                else
                {
                    break;
                }
            }
            if(j == chSub.length)
            {
                count++;
            }
        }
        return count;
    }
    
    static int matchCountKMP(String str, String sub)
    {
        char[] chStr = str.toCharArray();
        char[] chSub = sub.toCharArray();
        int[] next = getnext(sub);
        int count = 0;
        for(int i = 0; i < chStr.length; )
        {
            int j = 0;
            while(j < chSub.length && i < chStr.length) 
            {
                if(chStr[i] == chSub[j])
                {
                    i++;j++;
                    continue;
                }
                else
                {
                    if(next[j] != -1)
                    {
                        j=next[j];
                    }
                    else
                    {
                        i++;
                        break;
                    }
                }
            }
            if(j == chSub.length)
            {
                count++;
            }
        }
        return count;
    }
    

    static int[] getnext(String sub)
    {
        char[] chSub = sub.toCharArray();
        int[] next = new int[chSub.length];
        next[0] = -1;
        for(int i = 1; i < chSub.length; i++)
        {
            if(next[i-1] == -1 || chSub[i-1] == chSub[next[i-1]]){
                next[i] = next[i-1] + 1;
            }
            else
            {
                next[i] = 0;
            }
        }
        return next;
    }

 

评论

2 楼 lvwenwen 2013-04-04  

写一下注释吗

1 楼 xchd 2013-04-03  

能写一下注释吗