strStr

For a given source string and a target string, you should output the first index(from 0) of target string in source string.

If target does not exist in source, just return -1.

Example

If source = "source" and target = "target", return -1.

If source = "abcdabcdefg" and target = "bcd", return 1

看别人的博客偶尔提到播放器算法顺便写一写复习一下

两个注意的地方

一是输入检查 target 为空的情况直接返回0;

二是返回值计算的时候是sIndex-tIndex 而不是 sIndex-tIndex+1 （第一次跑搞错了）

 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     int[] p;
 9     public int strStr(String source, String target) {
10         // write your code here
11         if(source==null||target==null||target.length()>source.length()) return -1;
12         if(target.length()==0) return 0;
13         preProcess(target);
14         int sIndex =0, tIndex = 0;
15         
16         while(sIndex<source.length()){
17             if(source.charAt(sIndex)==target.charAt(tIndex)){
18                 sIndex++;
19                 tIndex++;
20             }else{
21                 if(tIndex>0){
22                     tIndex = p[tIndex];
23                 }else{
24                     sIndex++;
25                 }
26             }
27             if(tIndex==target.length()) return sIndex-tIndex;
28         }
29         return -1;
30         
31     }
32     private void preProcess(String target){
33         p = new int[target.length()];
34         int i=1;
35         while(i<target.length()){
36             int j = p[i-1];
37             while(j>0&&target.charAt(j)!=target.charAt(i)) j = p[j-1];
38             if(target.charAt(j)==target.charAt(i)){
39                 p[i] = j+1;
40             }
41             i++;
42         }
43     }
44 }