LintCode ---- 刷题总结

对于一个给定的 source 字符串和一个 target 字符串，你应该在 source 字符串中找出 target 字符串出现的第一个位置(从0开始)。如果不存在，则返回 -1。

基本：两重for循环，时间复杂度O(n^2)。

 1 class Solution {
 2     /**
 3      * Returns a index to the first occurrence of target in source,
 4      * or -1  if target is not part of source.
 5      * @param source string to be scanned.
 6      * @param target string containing the sequence of characters to match.
 7      */
 8     public int strStr(String source, String target) {
 9         //write your code here
10         if (source == null || target == null) {
11             return -1;
12         }
13         for (int i = 0; i < source.length() - target.length() + 1; i++) {
14             int j = 0;
15             for (j = 0; j < target.length(); j++) {
16                 if (source.charAt(i + j) != target.charAt(j)) {
17                     break;
18                 }
19             }
20             if (j == target.length()) {
21                 return i;
22             }
23         }
24         return -1;
25     }
26 }

View Code

高级：Rabin Karp算法，时间复杂度为O(n+m)，n为源字符串长度，m为目标字符串长度。该算法时间复杂度与KMP算法一样，但是比KMP简单，不建议使用KMP，不仅写起来麻烦而且容易错。

 1 public class Solution {
 2     private static int BASE = 1000000;
 3     /**
 4      * @param source a source string
 5      * @param target a target string
 6      * @return an integer as index
 7      */
 8     public int strStr2(String source, String target) {
 9         // Write your code here
10         if (source == null || target == null) {
11             return -1;
12         }
13         int m = target.length();
14         if (m == 0) {
15             return 0;
16         }
17         //31 ^ m
18         int power = 1;
19         for (int i = 0; i < m; i++) {
20             power = (power * 31) % BASE;
21         }
22         //targetCode
23         int targetCode = 0;
24         for (int i = 0; i < m; i++) {
25             targetCode = (targetCode * 31 + target.charAt(i)) % BASE;
26         }
27         //hashCode
28         int hashCode = 0;
29         for (int i = 0; i < source.length(); i++) {
30             hashCode = (hashCode * 31 + source.charAt(i)) % BASE;
31             if (i < m - 1) {
32                 continue;
33             }
34             if (i >= m) {
35                 hashCode = hashCode - (source.charAt(i - m) * power) % BASE;
36                 if (hashCode < 0) {
37                     hashCode += BASE;
38                 }
39             }
40             if (targetCode == hashCode) {
41                 if (source.substring(i - m + 1, i + 1).equals(target)) {
42                     return i - m + 1;
43                 }
44             }
45         }
46         return -1;
47     }
48 }

View Code

转载于:https://www.cnblogs.com/choumeng/p/6287558.html