ImplementstrStr [source code]

public class ImplementstrStr {
static
/******************************************************************************/
public class Solution {
    public int strStr(String haystack, String needle) {
        char[] chh = haystack.toCharArray();
        char[] chn = needle.toCharArray();
        int m = chh.length, n = chn.length; 
        for (int i = 0; i <= m - n; i++) {
            int j = 0;
            for (; j < n; j++) {
                if (chn[j] != chh[i + j]) break;
            }
            if (j == n) return i;
        }
        return -1;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        ImplementstrStr.Solution tester = new ImplementstrStr.Solution();
        String[] inputs = {
            "ABABDABACDABABCABAB", "ABABCABAB", "10",
        };
        for (int i = 0; i < inputs.length / 3; i++) {
            String haystack = inputs[3 * i];
            String needle = inputs[1 + 3 * i];
            int expected = Integer.parseInt(inputs[2 + 3 * i]);
            System.out.println(Printer.seperator());
            Printer.openColor("magenta");
            System.out.print(haystack + " AND " + needle);
            Printer.closeColor();
            int output = tester.strStr(haystack, needle);
            System.out.print(" -> " + output + ", ");
            Printer.openColor(output == expected ? "green" : "red");
            System.out.println("expected: " + expected);
            Printer.closeColor();
        }
    }
}

这个题目本身是很熟悉了, 就是一个最常规的substring search, 问题是怎么做. 当然最好的办法估计还是KMP, 不过我们还是先用笨办法来做;

穷搜的方法还是要会的, Sedgwick上面也是介绍过的. 最后的速度是7ms (75%), 还算可以接受. KMP在text比较短的情况下优势并不明显, 所以这里穷搜也能达到不错的速度;

回头有时间自己再来把KMP实现一遍.

这个是C++的写法, 因为C++可以直接出界, 所以判断terminating condition反而变得直白:

int strStr(char *haystack, char *needle) {  
    if (!haystack || !needle) return -1;  
    for (int i = 0; ; ++i) {  
        for (int j = 0; ; ++j) {  
            if (needle[j] == 0) return i;  
            if (haystack[i + j] == 0) return -1;  
            if (haystack[i + j] != needle[j]) break;  
        }  
    }  
}

这个是整合到一个循环的代码:

int strStr(char *haystack, char *needle) {  
    if (!haystack || !needle) return -1;  
    for (int i = 0; ; ++i) {  
        for (int j = 0; ; ++j) {  
            if (needle[j] == 0) return i;  
            if (haystack[i + j] == 0) return -1;  
            if (haystack[i + j] != needle[j]) break;  
        }  
    }  
}

这个就是明确的实现了backup i 的操作. 看起来这个的工作量好像小一点, 但是实际上是一样的;

discussion上有人用了另外一个算法, 源代码保存在这里:
I used Rabin-Karp algorithm and it is accepted.

class Solution {  
public:  
    char *strStr(char *haystack, char *needle) {  
        int lenT = 0;  
        int lenP = 0;  
        while (haystack[lenT] != '\0'){  
            ++lenT;  
        }  
        while (needle[lenP] != '\0'){  
            ++lenP;  
        }  
        const int base = 256;  
        const int prime = 127;  
        int h = 1;  
        for (int i = 0; i< lenP-1; ++i){  
            h = (h*base)%prime;  
        }  
        int hashP = 0;  
        int hashT = 0;  
        for (int j = 0; j<lenP;++j){  
            hashP = (base*hashP+needle[j])%prime;  
            hashT = (base*hashT+haystack[j])%prime;  
        }  
        for (int s = 0; s<=(lenT-lenP); ++s){  
            if (hashP == hashT){  
                if(isPattern(haystack+s, needle,lenP)) return (haystack+s);  
            }  
            if (s<(lenT-lenP)){  
                hashT = (base*(hashT-haystack[s]*h) + haystack[s+lenP])%prime;  
                if (hashT<0){  
                    hashT +=prime;  
                }  
            }  
        }  
        return NULL;  
    }  
    bool isPattern(char* haystack, char* needle, int m){  
        for (int i = 0; i<m; ++i){  
            if (haystack[i] != needle[i]){  
                return false;  
            }  
        }  
        return true;  
    }  
};

Problem Description

Implement strStr().

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

Difficulty:Easy
Total Accepted:189K
Total Submissions:676.9K
Contributor: LeetCode
Companies
pocket gems microsoft apple facebook
Related Topics
two pointers string
Similar Questions
Shortest Palindrome Repeated Substring Pattern