LeetCode: strStr

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

我以为不就是找个字符串吗,扫描一遍不就行了。。后来才发现,原来面试的时候不让用这种方法,都考出花了。

所以学习了一下KMP算法。具体内容有链接。

LeetCode: strStr
 1 public static String kmp(String haystack, String needle) {
 2         if (needle.length() == 0) return haystack;
 3         if (haystack.length() == 0) return null;
 4         if (haystack.length() < needle.length()) return null;
 5         
 6         int[] next = new int[needle.length()];
 7         next = kmpNext(needle);
 8         
 9         for (int i = 0, j = 0; i < haystack.length(); i++) {
10           while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
11               j = next[j - 1];
12           }
13           
14           if (haystack.charAt(i) == needle.charAt(j))
15               j++;
16           //match successfully
17           if (j == needle.length())
18               return haystack.substring(i-j+1);
19       }
20       return null;
21     }
22 
23     public static int[] kmpNext(String needle) {
24         int[] next = new int[needle.length()];
25         if (needle.length() == 0) return next;
26         next[0] = 0;
27         for (int i = 1, j = 0; i < needle.length(); ++i) {
28             while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
29                 j = next[j - 1];
30             }
31 
32             if (needle.charAt(i) == needle.charAt(j)) 
33                 ++j;
34 
35             next[i] = j;
36         }
37         return next;
38     }
LeetCode: strStr

 

http://biaobiaoqi.me/blog/2013/05/25/kmp-algorithm/

http://blog.csdn.net/v_july_v/article/details/7041827

LeetCode: strStr

上一篇:第3阶段 Kali Linux入门教程 课时4桌面环境


下一篇:一步一步生成图片水印