Implement strstr

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.

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, …?

Leave a Reply

Using Gravatars in the comments - get your own and be recognized!

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