LeetCode刷题day09|28. 找出字符串中第一个匹配项的下标_leetcode 28. 找出字符串中第一个匹配项的下标

找出字符串中第一个匹配项的下标

在数据结构中学习KMP算法，仅仅只是理解它的原理，但并没有它具体怎样通过代码实现，今天跟着卡哥学习了怎样用代码实现KMP算法，收获还是很大的。
首先，在使用KMP算法的时候，一定要先建立一个前缀表next[],前缀表依据代码的实现方式有三种形式，这里，主要讲其中一种。
创建前缀表主要由四步组成，依据这四步，可以轻松创建。

1. 初始化
   将j赋值为0，next[j]也赋值为0。
2. 对不匹配的字符进行处理
   这里注意使用的是while，因为：如果两个字符不想等，就继续向前找寻相等的字符。直到相等或者j=0。
3. 对匹配的字符进行处理
   这里使用if判断，如果相等，j++（i++在for语句里有写，这里不需要再额外写）
4. 更新next[]
   将j的数值赋给next[i]

以下是代码部分：

private void getNext( String s , int[] next){

        //一、初始化
        int j = 0;
        next[0] = 0;

        for (int i = 1; i < s.length(); i++) {


            //二、不匹配
            while (s.charAt(i) != s.charAt(j) && j>0)
                j = next[j-1];

            //三、匹配
            if( s.charAt(i) == s.charAt(j))
                j++;

            //四、更新next
            next[i] = j;

        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

在对文本串进行模式串的匹配的时候，其实就跟创建前缀表next[]基本完全一样，因为都是在找两处相等的字符串。区别是：

1. 前缀表只在模式串操作，而这个是分别在文本串和模式串操作。
2. 前缀表i从1开始（0已经初始化了），而这个中的i则是从0开始
3. 前缀表需要在第四步更新next[]，而这个在第四步中是比较j是否已经等于模式串的长度（即是否已匹配完）

以下是代码部分，两个方法的代码基本相同：

public  int strStr(String haystack, String needle) {

        //一、初始化
        int[] next = new int[needle.length()];
        int j =0;
        getNext(needle,next);

        for (int i = 0; i < haystack.length(); i++) {

            //二、不匹配
            while ( haystack.charAt(i) != needle.charAt(j) && j>0)
                j = next[j-1];

            //三、匹配
            if(haystack.charAt(i) == needle.charAt(j))
                j++;

            //四、判断j的大小
            if( j == needle.length())
                return i-j+1;

        }
        return -1;
    }


    private void getNext( String s , int[] next){

        //一、初始化
        int j = 0;
        next[0] = 0;

        for (int i = 1; i < s.length(); i++) {


            //二、不匹配
            while (s.charAt(i) != s.charAt(j) && j>0)
                j = next[j-1];

            //三、匹配
            if( s.charAt(i) == s.charAt(j))
                j++;

            //四、更新next
            next[i] = j;

        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49