Leetcode: Implement strStr()

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

Solution:

We first preprocess the needle, in such a way that we obtain the equivalent states, for instance:

   a a b a a b c
   0 0 1 0 1 2 3

That means that if we are have found aabaab, we have also found aab. When we process the haystack, when we arrive to a state that we cannot go on, we change to its previous equivalent state.

public class Solution {
    public String strStr(String haystack, String needle) {
        if(needle.length()==0)
            return haystack;
        int[] previousState = new int[needle.length()];
        previousState[0] = 0;
        int previousEqState=0;
        for(int i=1; i<needle.length(); i++)
        {
            previousState[i] = previousEqState;
            if(needle.charAt(i)==needle.charAt(previousEqState))
                previousEqState++;
            else
                previousEqState = 0;
        }
        
        int lettersFound = 0;
        int position = 0;
        while(position<haystack.length())
        {
            if(haystack.charAt(position) == needle.charAt(lettersFound))
            {
                position++;
                lettersFound++;
                if(lettersFound == needle.length())
                    return haystack.substring(position-needle.length());
            }
            else
            {
                if(lettersFound>0)
                    lettersFound = previousState[lettersFound];
                else
                    position++;
            }
        }
        return null;
    }
}