Implement strStr() （匹配字符串有关问题，哈希解法） 【leetcode】

Implement strStr() （匹配字符串问题，哈希解法） 【leetcode】

题目：Implement strStr().

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

暴力就不说了，kmp也做多了，我写了一个哈希处理的方法，复杂度也是O（n）。

因为都是小写字母，每次进位乘27就能保证没有冲突，先计算子串的哈希值，在遍历原串匹配是否有相同的哈希值。

const long long M=1<<29+1;const int H=27;class Solution {public:    char *strStr(char *haystack, char *needle) {        long long hashne,phash;        hashne=phash=0;        int i,j;        int len=strlen(haystack),k=1;        int len2=strlen(needle);        if(len<len2)return NULL;        else if(len2==0)return haystack;        for(i=0;i<len2;++i)        {            hashne=(hashne*H+(needle[i]-'a'))%M;             phash=(phash*H+(haystack[i]-'a'))%M;            k=(k*H)%M;        }        for(j=0;i<=len;++j,++i)        {            if(hashne==phash)return haystack+j;            phash=(H*phash-k*(haystack[j]-'a')+haystack[i]-'a'+M)%M;        }        return NULL;    }};