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 < 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 >= 0 && needle[pos] != needle[cnd]) cnd = T[cnd];
                pos = pos + 1;
                cnd = cnd + 1;
            }
        }
        
        while (m+i < 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] > -1){
                    m = m+i-T[i];
                    i = T[i];
                } else {
                    m = m + i + 1;
                    i = 0;
                }
            }
        }
        return -1;
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *