LeetCode 28. Implement strStr()

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

解析：
查找子串needle第一次出现在字符串haystack的下标，如果不存在则返回-1.
方法1
此题最容易想到的时暴力求解，依次遍历haystack中的每个元素，判断是否与needle的第一个元素相同，如果相同则挨个比较needle的剩余元素。具体代码如下：
[cc lang=”C++”]
class Solution {
public:
int strStr(string haystack, string needle) {
if(needle.length()==0)
{
return 0;
}else if(haystack.length() <=0 || needle.length() > haystack.length())
return -1;
char first_char = needle[0];
bool flag = false;
int index = -1;
for(int i=0; i< haystack.length(); i ++) { if(first_char == haystack[i]) { index = i; for(int j=i,k=0;k<needle.length()&&j<haystack.length();j++,k++) {=”” if(haystack[j]=”” !=”needle[k])” break;=”” if=”” (k=”=needle.length()-1)” flag=”true;” }=”” if(flag)=”” if(!flag)=”” index=”-1;” return=”” index;=”” };=”” [=”” cc]=”” 很可惜这种方法会超时。=”” <strong=””>

方法2
其实我们没有必要遍历整个字符串，只需要遍历到剩余字符串长度与目标字符长度相等即可。对于子字符串，依次遍历，如果不相等则跳出循环。优化后的代码如下：

class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.empty())
            return 0;
        int source_len = haystack.length();
        int target_len = needle.length();
        int j = 0;
        for(int index = 0; index <= source_len - target_len; index ++)
        {
            for(int j= 0; j < target_len; j++)
            {
                if(haystack[index+j] != needle[j])
                    break;
                if(j == target_len -1)
                    return index;
            }           
        }
        return -1;
    }
};

优化效果很明显。

方法3
采用KMP算法。主要思想是在匹配时充分利用已经匹配的信息，当前面字符匹配成功，匹配第i个元素失败时，不是往后移动一个元素，而是根据移动位数=已经匹配数目-对应的匹配数值。具体KMP算法介绍请参见：http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
这里直接搬运别人的代码，具体代码如下：
[cc lang=”C++”]
public class Solution {
public int strStr(String haystack, String needle) {
if(needle.length() == 0){
return 0;
}
int[] next = new int[needle.length()];
// 得到next数组
getNextArr(next, needle);
// i是匹配串haystack的指针，j是模式串needle的指针
int i = 0, j = 0;
// 双指针开始匹配
while(i < haystack.length() && j < needle.length()){ // 如果j=-1意味着刚刚失配过，下标+1后，下一轮就可以开始匹配各自的第一个了 // 如果指向的字母相同，则下一轮匹配各自的下一个 if(j == -1 || haystack.charAt(i) == needle.charAt(j)){ i++; j++; // 如果失配，则将更新j为next[j] } else { j = next[j]; } } return j == needle.length() ? i – j : -1; } private void getNextArr(int[] next, String needle){ // k是前缀中相同部分的末尾，同时也是相同部分的长度，因为长度等于k-0。 // j是后缀的末尾，即后缀相同部分的末尾 int k = -1, j = 0; next[0] = -1; while(j < needle.length() – 1){ // 如果k=-1，说明刚刚失配了，则重新开始计算前缀和后缀相同的长度 // 如果两个字符相等，则在上次前缀和后缀相同的长度加1就行了 if (k == -1 || needle.charAt(j) == needle.charAt(k)){ k++; j++; next[j] = k; } else { // 否则，前缀长度缩短为next[k] k = next[k]; } } } } [/cc] 参考：http://www.cnblogs.com/grandyang/p/4606696.html http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html https://segmentfault.com/a/1190000003707284 </needle.length()&&j<haystack.length();j++,k++)>