LeetCode/src/easy/ImplementstrStr.java at master · chenyiAlone/LeetCode · GitHub

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
package easy;

import static util.Utils.*;
/**
 *
 * ClassName: ImplementstrStr
 * @author chenyiAlone
 * Create Time: 2018/12/04 17:30:29
 * Description: No.28 匹配字符串，最好的方法应该是使用KMP算法
 */
public class ImplementstrStr {
    /**
     * 暴力搜索
     * @param haystack
     * @param needle
     * @return
     */
    public int strStr(String haystack, String needle) {
        boolean flag;
        if (haystack.equals("") && needle.equals("")) return 0;
        for (int i = 0; i < haystack.length(); i++) {
           flag = true;
           if (needle.length() + i > haystack.length()) return -1;
           for (int j = 0; j < needle.length(); j++) {
               if (haystack.charAt(i + j) != needle.charAt(j))  {
                   flag = false;
                   break;
               }
           }
           if (flag) {
               return i;
           }
       }
        return -1;
    }

    /**
     * kmp算法的查找
     * @param haystack
     * @param needle
     * @return
     */
    public int strStrByKmp(String haystack, String needle) {
        return kmpSearch(haystack, needle);
    }
    public static int[] kmpArray(String needle) {
        int[] nums = new int[needle.length() + 1];
        nums[0] = -1;
        nums[1] = 0;
        int len = 0;
        int i = 2, n = needle.length();
        while (i < n) {
            if (needle.charAt(len) == needle.charAt(i)) {
                len++;
                nums[i + 1] = len;
                i++;
            } else {
                if (len > 0) {
                    len = nums[len];
                } else {
                    nums[i + 1] = len;
                    i++;
                }
            }
        }
        return nums;
    }
    public static int kmpSearch(String haystack, String needle) {
        int kmp[] = kmpArray(needle);
        printArray(kmp);
        int i = 0, j = 0, n = haystack.length(), m = needle.length();
        while (i < n) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                if (j == m - 1) {
                    System.out.println(i - j);
                     return i - j;
//                    j = kmp[j];
                }
                j++;
                i++;
            } else {
                j = kmp[j];
                if (j == -1) {
                    i++;
                    j++;
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        String haystack = "ababcd";
        String needle = "abc";
//        System.out.println(new ImplementstrStr().strStr(haystack, needle));
//        printArray(kmpArray(needle));
        kmpSearch(haystack, needle);
    }
}