# My 4ms C++ solution, it used the kmp algorithm.

• class Solution {
public:

``````// get the "next" array
vector<int> getNext(string &s) {
int length = s.size();
vector<int> next(length);
next[0] = 0;
for (int i = 1,q = 0; i < length;i++) {
while (q > 0 && s[i] != s[q])
q = next[q-1];
if (s[i] == s[q])
q++;
next[i] = q;
}
return next;
}
// use kmp algorithm to judge if the first string can match the second string
int kmp(string &s1,string &s2) {
int length1 = s1.size(),length2 = s2.size();
if (length1 < length2)
return false;
vector<int> next = getNext(s2);
for (int i = 0, q= 0; i < length1;i++) {
while (q > 0 && s1[i] != s2[q])
q = next[q-1];
if (s1[i] == s2[q])
q++;
if (q == length2)
return i-q+1;
}
return -1;
}

int strStr(string haystack, string needle) {
if (needle.empty()) return 0;
if (haystack.empty()||haystack.size() < needle.size()) return -1;
return kmp(haystack,needle);
}
``````

};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.