# Are we expected to use KMP for this problem?

• Is it the standard string matching problem? Am I wrong?

• It is definitely solvable using KMP

• No, it is not expected to use KMP for this problem. But it is a good exercise for those who are interested.

• There is a useful thread created by 1337 years back.
http://leetcode.com/2010/10/implement-strstr-to-find-substring-in.html

• @1337, please consider to break this strStr problem into two problems. The second problem (strStr II) can add a complexity constraint.

• You can use KMP to solve it, but actually it is expected to use optimized brute-force search(i got AC use such one), just take care about several tricky cases if you got TLE result.

• just for reference,KMP + the trick mentioned in 1337's post

``````class Solution {
public:
char *strStr(char *S, char *T) {
if(!S||!T)return NULL;
if(!*T)return S;
int Plen = strlen(T);
int *next = new int[Plen+1];
initKMP(T,next,Plen);
int i=0,j = 0;//i for S,j for T
for(i=0;j<Plen&&*(S+i);){
if(S[i]==T[j]){
i++;j++;
}else if(next[j]>=0){
j = next[j];
}else{
i++;
j = 0;
if(!*(S+i+Plen-1))break;
}
}
if(j>=Plen)return S+i-Plen;
else return NULL;
}

void initKMP(char str[],int next[],int len){
int i=0,j=-1;
next[0] = -1;
while(i<len){
while(j>=0&&str[i]!=str[j])j = next[j];
i++;j++;
if(str[j]==str[i])next[i] = next[j];
else next[i] = j;
}
}
};
``````

• 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;
}
};``````

• simple implementation not using KMP

`````` char *strStr(char *haystack, char *needle) {
int len = strlen(needle);
int len2 = strlen(haystack);
int n=0;
if(*needle){
while(haystack[n]){
int i,j;
for(i=0,j=len-1;i<=j && n+j < len2 ;i++,j--){
if(*(haystack+n+i)!=*(needle+i) || *(haystack+n+j)!=*(needle+j))
break;
}
if(i>j)
return &haystack[n];
n++;
}
return NULL;
}else
return haystack;

}``````

• Just another version with Rabin-Karp algorithm.

``````public class Solution {
long R = 31L;
long M = 10000000000000003L;
long RK; // R^(pattern.length) % M

public String strStr(String haystack, String needle) {
if (haystack == null || needle == null || haystack.length() < needle.length())
return null;
if(needle.length() == 0)
return haystack;

long target = hash(needle, 0, needle.length() - 1);
long hash = hash(haystack, 0, needle.length() - 1);

RK = 1;
for (int i = 0; i < needle.length(); i++) {
RK = (RK * R) % M;
}
RK %= M;

if (hash == target)
return haystack;
for (int i = 1; i <= haystack.length() - needle.length(); i++) {
long tmp = nextHash(hash, haystack.charAt(i - 1), haystack.charAt(i + needle.length() - 1));
if (tmp == target)
return haystack.substring(i);
hash = tmp;
}
return null;
}

long hash(String s, int start, int end) {
long sum = 0;
for (int i = start; i <= end; i++) {
sum = sum * R % M + (int) s.charAt(i) % M;
}
return sum % M;
}

long nextHash(long hash, char oldFirst, char next) {
long a = hash * R % M;
long b = next % M;
long c = oldFirst % M * RK % M;

return (a + b - c + M) % M;
}
}``````

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