首页 > 代码库 > 28. Implement strStr()

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.

 

 

字符串Rabin--Karp算法。滚动哈希,时间复杂度o(n+m),觉得比kmp好写

class Solution {public:    const unsigned long long T = 100000007;    int strStr(string haystack, string needle) {        typedef unsigned long long ull;        int al = needle.length();        int bl = haystack.length();        if (al > bl) return -1;        ull A = 0;        ull B = 0;        ull t = 1;        for (int i = 0; i < al; ++i) {            A = A * T + needle[i];            B = B * T + haystack[i];            t *= T;        }        //cout << A << " "<<B<<endl;        for (int i = 0; i + al <= bl; ++i) {            if (A == B) return i;            if (i + al < bl) B = B * T - t * haystack[i] + haystack[i + al];        }        return -1;    }};

 

28. Implement strStr()