# LeetCode 28. Implement strStr()

Implement strStr().

This problem can be solved easily but a O(n2) brute force, for it can be solved by a O(n) KMP algorithm, but KMP is hard to remember…

```public class Solution {
public int StrStr(string haystack, string needle) {
if (haystack == null || haystack == ""){
if (needle == "" || needle == null) return 0;
else return -1;
}
if (needle == "" || needle == null) return 0;

int m = 0;
int i = 0;
int[] T = new int[needle.Length];

int pos = 1;
int cnd = 0;
T[0] = -1;
while (pos &lt; needle.Length){ if(needle[pos] == needle[cnd]){ T[pos] = T[cnd]; pos = pos+1; cnd = cnd+1; } else { T[pos] = cnd; cnd = T[cnd]; while(cnd &gt;= 0 &amp;&amp; needle[pos] != needle[cnd]) cnd = T[cnd];
pos = pos + 1;
cnd = cnd + 1;
}
}

while (m+i &lt; haystack.Length) { if (needle[i] == haystack[i+m]) { i = i + 1; if (i == needle.Length) { return m; m = m+i-T[i]; i = T[i]; } } else { if (T[i] &gt; -1){
m = m+i-T[i];
i = T[i];
} else {
m = m + i + 1;
i = 0;
}
}
}
return -1;
}
}
```