3 Solutions and approximate to o(n+k)


  • 0
    C
    public class Solution {
        private const int MINFASTLEN = 100;
        private const int p = 100008;
        
        public int StrStr(string haystack, string needle){        
            return StrStr_Faster(haystack, needle);
        }
        
        // first hash the needle and compare to sliding window on haystack.
        // if match hash, check whether the string are exact match. 
        // Suppose the hash is good enough to have const number of conflicts, say c, the approximate time complexity should be O(c(n+k)) = O(n+k)
        public int StrStr_Faster(string haystack, string needle){
            if (String.IsNullOrEmpty(needle)) return 0;
            if (haystack == null || needle == null) return -1;
            
            int needleHash = 0;
            var posWeight = 1;
            for (int i = 0; i < needle.Length; i++){
                needleHash = ((needleHash << 1) + (int)needle[i]) % p;            
            }
            for (int i = 1; i < needle.Length; i++){
                posWeight = (posWeight << 1) % p;            
            }
            
            int slideHash = 0;
            for (int i = 0; i < haystack.Length; i++)
            {
                if (i >= needle.Length){
                    slideHash = (((slideHash - posWeight * haystack[i - needle.Length]) % p) + p) % p;
                }
                slideHash = ((slideHash << 1) + haystack[i]) % p;
                if (i + 1 >= needle.Length && slideHash == needleHash){
                    int j = 0;
                    while (j < needle.Length && haystack[i - needle.Length + 1 + j] == needle[j]) j++;
                    if (j == needle.Length) return i - needle.Length + 1;
                }
            }
            return -1;
        }
        
        // use KMP to improve the long and sub-duplicated needle
        public int StrStr_Fast(string haystack, string needle) {
            if (String.IsNullOrEmpty(haystack) && String.IsNullOrEmpty(needle)) return 0;
            if (haystack == null || needle == null) return -1;
            var pointers = BuildFailPointers(needle);
            var validStart = haystack.Length - needle.Length;
            for (int i = 0, j = 0; i <= validStart; )
            {
                while (j < needle.Length && i + j < haystack.Length && haystack[i + j] == needle[j]) j++;
                if (j == needle.Length) return i;            
                j = pointers[j] + 1;
                i += j + 1;
            }
            return -1;
        }
    
        // basic implementation, O(n^2) force find
        public int StrStr_Slow(string haystack, string needle) {
            if (String.IsNullOrEmpty(haystack) && String.IsNullOrEmpty(needle)) return 0;
            if (haystack == null || needle == null) return -1;
            var validStart = haystack.Length - needle.Length;
            for (int i = 0; i <= validStart; i++){
                int j = 0;
                while (j < needle.Length && haystack[i + j] == needle[j]) j++;
                if (j == needle.Length) return i;
            }
            return -1;
        }
        
        private int[] BuildFailPointers(string str){
            if (String.IsNullOrEmpty(str)) return new int[0];
            var pointers = new int[str.Length];
            pointers[0] = -1;
            for (int i = 1; i < str.Length; i++){
                int j = pointers[i - 1];
                while (j >= 0 && str[j + 1] != str[i]){
                    j = pointers[j];
                }
                if (j < 0) pointers[i] = -1;
                else pointers[i] = j + 1;            
            }
            return pointers;
        }
    
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.