字符串匹配相关算法

今天无意间碰到了需要写子字符串匹配得算法，由于以前一直对字符串得KMP算法不太了解，所以今天趁着这个机会正好记录下这三种算法的差异：

1. JavaApi实现
2. 朴素字符串匹配算法
3. KMP算法

Java的API实现子字符串查找：

在Java的String类里面有一个方法是indexof(str,index), 这个类的话是可以从一个字符串的指定位置查出是否包含子字符串，若不包含则返回的是-1，若包含的话则返回的是该子字符串在字符串中的索引位置。 那么这个算法是什么原理呢，这个算法的原理就是indexof会返回匹配到的字符串的索引，那么当这个算法匹配到了一个之后获取返回的索引，然后再加上字符串的长度，最后再在剩下的字符串里面匹配，便会得出所有的字符串个数。

public void test(){
        String findText= "abcd";
        String srcText ="mabcdfafasabcdfa";
        int count = 0;
        int index = 0;
        while ((index = srcText.indexOf(findText, index)) != -1) {
        index = index + findText.length();
         count++;
        }
        System.out.println(count);
    }

朴素字符串匹配算法：

这个算法就是两层循环，首先第一层循环便利需要字符串，获取第一个字符，然后进行第二层的循环，第二层的循环主要是进行子字符串，当子字符串的第一个字符和外面的字符串当前的字符相同的话，然后进行子字符串的第二个字符与外层的当前位置的第二个字符比较：

public void test1(){
       String a ="abcd";
       String b="qweabcdaefgadfabcdojfojaofoafjabcdafsaf";
       int count=0;
       for(int i =0 ;i<b.length() ;i++){
           int index=i;
           boolean flag =false;
           for(int j=0;j<a.length() ;j++){
               char c =b.charAt(index);
               if(a.charAt(j) == c){
                   index++;
               }else{
                   flag=true;
                   break;
               }
           }
           if(!flag) {
               count++;
           }
       }
        System.out.println(count);
    }

在这个里面需要注意的就是外层的i需要保存，同时里面的循环j是不需要的，因为子字符串是每一次都会遍历的。

KMP算法：

kmp算法所解决的问题是朴素字符串匹配算法每次匹配失败之后都要从头再来进行匹配的一个难点。在KMP算法中的： 匹配失败的话首先会检查匹配失败的头一个字符的的前缀和后缀，然后用以匹配的字符数减去其前缀和后缀的那个值，最后得出需要后退的数字，最后再在退出的步数上进同样的操作，最后再得出结论，当子字符串的第一个字符都不相匹配的时候最后子字符串整体后移一位。

关于Next数组的求法：

今天看了下资料总算了解了写KMP的Next数组的求法。现在一般来讲是有两种求法，第一种是求出匹配失败后的跳转索引的数组。第二种则是求出数组中已经匹配的前后缀的数组。这两种数组的求法都会导致再以后的计算出现不同的结果，但是最后还是需要用到的一个原理就是匹配失败：回退步数就是已经匹配的字符数减去匹配的前后缀字符数。最后得出回退步数。

目前来讲有两种next数组的求法：

1. 将前缀后缀匹配数放置到数组中
2. 将失败后回退的位置放置在数组中

对于第一种next数组来说，网上的资料多是将其后移一位，例如字符串abcab他的前缀和后缀数组是[0,0,0,1,2]，那么网上其他人的写法多是将这个数组再右移一位,最后为[-1,0,0,0,1]。在今天，也自己尝试了写KMP算法，但是自己的写法没有做右移操作，而是直接求解，如下：

public  static void generateNextArray(String str ,int[] array) {
        if (null == str || str.length() == 0) {
            return;
        }
        int i = 0;
        int j = 1;
        array[0] = 0;
        for (; j < str.length(); ) {
            if (str.charAt(i) == str.charAt(j)) {
                i++;
                j++;
                array[j - 1] = i;
            } else if(i!= 0 && j!=0) {
                i = array[i-1];  //这里需要i-1是因为最后需要数组右移一位，但是我这里没有移位，所以直接在这里减一
            }else{
                array[j]=i;
                j++;
                }
            }
        }

上面这个求next数组的方法其实也挺简单的，但是这里需要注意的是第二个if和第三个的else，为什么这里会出现两个是因为这里需要注意的情况会有两种，第二个if捕获的是在后续出现了断层需要重新从0开始匹配的情况。而最后一个else则是捕获的从头开始的一种情况，具体以abcdeabcdabcdeabcdfg做测试便会了解。
而网上的其他算法不需要这三个判断是因为网上的匹配失败之后K会变成-1，然后j是不变的。如下：

void getNext(String pattern, int next[]) {
        int j = 0;
        int k = -1;
        int len = pattern.length();
        next[0] = -1;

        while (j < len - 1) {
            if (k == -1 || pattern.charAt(k) == pattern.charAt(j)) {
                j++;
                k++;
                next[j] = k;
            } else {
                k = next[k];
            }
        }

    }

也就是说网上的一旦匹配失败，k就会变成next[next[k]]的值。

JDK中的indexOf方法：

再Java中的indexOf方法则是使用的朴素字符串匹配算法。如下：

static int indexOf(char[] source, int sourceOffset, int sourceCount,
            char[] target, int targetOffset, int targetCount,
            int fromIndex) {
        if (fromIndex >= sourceCount) {
            return (targetCount == 0 ? sourceCount : -1);
        }
        if (fromIndex < 0) {
            fromIndex = 0;
        }
        if (targetCount == 0) {
            return fromIndex;
        }

        char first = target[targetOffset];
        int max = sourceOffset + (sourceCount - targetCount);

        for (int i = sourceOffset + fromIndex; i <= max; i++) {
            /* Look for first character. */
            if (source[i] != first) {
                while (++i <= max && source[i] != first);
            }

            /* Found first character, now look at the rest of v2 */
            if (i <= max) {
                int j = i + 1;
                int end = j + targetCount - 1;
                for (int k = targetOffset + 1; j < end && source[j]
                        == target[k]; j++, k++);

                if (j == end) {
                    /* Found whole string. */
                    return i - sourceOffset;
                }
            }
        }
        return -1;
    }