LintCode(13) strStr

strstr (a.k.a find sub string), is a useful function in string operation. Your task is to implement this function.

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.

Have you met this question in a real interview? 

Yes

Example

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

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

Challenge

O(n2) is acceptable. Can you implement an O(n) algorithm? (hint: KMP)

Clarification

Do I need to implement KMP Algorithm in a real interview?

• Not necessary. When you meet this problem in a real interview, the interviewer may just want to test your basic implementation ability. But make sure your confirm with the interviewer first.

 这道题目的o(n)的解法大概有两个: KMP 或者是boyer-moore算法， 写起来也费尽，也不是面试中能很快写出来的。所以暴力解法，o(n^2)就算够了， 我觉得考察三个地方： 1） corner case: 空指针 2） corner case: 空字符串 3） 对c style字符指针的应用 遍历每一个source的字符 遍历中比较source leading char以后的字符和target字符，如果比较完则*target='\0'.那么则可返回， 否则继续source的遍历。

1:  class Solution {  
2:  public:  
3:    /**  
4:     * Returns a index to the first occurrence of target in source,  
5:     * or -1 if target is not part of source.  
6:     * @param source string to be scanned.  
7:     * @param target string containing the sequence of characters to match.  
8:     */  
9:    int strStr(const char *source, const char *target) {  
10:      // write your code here  
11:      // corner cases:  
12:      // 1. null ptr  
13:      if (!source || !target){  
14:        return -1;  
15:      }  
16:      // 2. contains '\0'  
17:      if (!*target){  
18:        return 0;  
19:      }  
20:      // double loop for scan o(n^2)  
21:      int index=0;  
22:      while(*source){  
23:        const char* tmp_source=source;  
24:        const char* tmp_target=target;  
25:        while(*tmp_source && *tmp_target && *tmp_source==*tmp_target){  
26:          tmp_source++;  
27:          tmp_target++;  
28:        }  
29:        if (!*tmp_target){  
30:          return index;  
31:        }  
32:        source++;  
33:        index++;  
34:      }  
35:      return -1;  
36:    }  
37:  };