# Implement strstr

Question: Implement strstr in Java. Find the first instance of a string in another string.

```public int Search(String haystack, String needle){
for(int i = 0; i < haystack.length(); i++ ) {
for(int j = 0; j < needle.length() &&
i+j < haystack.length(); j++ ) {
if(needle.charAt(j) != haystack.charAt(i+j)) {
break;
} else if (j == needle.length()-1) {
return i;
}
}
}
return -1;
}
```

Like this question? Follow our feed and tweet it.

If you're looking for some serious preparation for your interviews, I'd recommend this book written by a lead Google interviewer. It has 189 programming questions and solutions:  ## 4 Responses

1. Abhijit says:

Complexity is n square. Can we do it better than this?

2. Mihai Roman says:

This is the rather naive implementation, however accurate. You should take a look at the Knuth-Morris-Pratt (KPM) algorithm:

http://en.wikipedia.org/wiki/Knuth-morris-pratt

3. Nils says:

Didn’t know about indexOf.. but this would make it too simple.

Here is what I did.
``` /** * Returns the position where the substring toFind in s starts. -1 if it's not found. * @param s * @param toFind * @return */ static int strStr(String s, String toFind) {```

``` int pos = -1; int i = 0, j = 0; for(; i<s.length(); i++) { if(j == toFind.length()) { return pos; } if (pos == -1 && s.charAt(i) == toFind.charAt(0)) { pos = i; j = 1; continue; } else if (s.charAt(i) == toFind.charAt(j)) { j++; } else { j = 0; pos = -1; } } ```

``` return pos; } ```

4. Steffen says:

Isn’t this simply a String.indexOf(String str)? Which strstr do you mean, the C, PHP, …?

XHTML: These are some of the tags you can use: `<a href=""> <b> <blockquote> <code> <em> <i> <strike> <strong>`