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

**Answer:**

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.

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

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

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

}

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