Strstr use hash


  • -1
    C
    class Solution {
    public:
        int strStr(string haystack, string needle) {
                  setHashValue(haystack);
             int haystack_len=haystack.length();
            int needle_len=needle.length();
            setPower(haystack_len);
            hashValueType needleHashValue=getHashValue(needle);
            for(int i=0;i<haystack_len-needle_len+1;++i)
    		{
             hashValueType substrVal=hashVal[i+needle_len]-hashVal[i]*power[needle_len];
            if(substrVal==needleHashValue){
                return i;
            }
    		}
            return -1;
        }
    private:
    	 typedef unsigned long long hashValueType;
         static const int maxn = 1000;
         static const int B = 17;
        hashValueType hashVal[maxn];
        hashValueType power[maxn];
         hashValueType getHashValue(const string &str){
            hashValueType val=0;
            int len=str.length();
            for(int i=0;i<len;++i){
                val=val*B+str[i];
            }
            return val;
        }
        void setHashValue(const string&str){
            int len=str.length();
            hashVal[0]=0;
            for(int i=0;i<len;++i)
            hashVal[i+1]=hashVal[i]*B+str[i];
        }
        void setPower(int n){
            power[0]=1;
            for(int i=1;i<=n;++i){
                power[i] = power[i-1] * B;
            }
        }
    };
    runtime error,I don't know why,if someone knows please tell me!

Log in to reply
 

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