leetcode(力扣)第二十八题:实现 strStr()_C++

class Solution {
public:
    void GetNextval(string t,int nextval[]){
    	int j=0,k=-1;
    	nextval[0]=-1;
       	while (j<t.length()-1){
           	if (k==-1 || t[j]==t[k]) {	
	    		if(t[++j]!=t[++k])  nextval[j]=k;
           	    else    nextval[j]=nextval[k];
       	    }
       	    else  k=nextval[k];    	
	    }
    }
    int KMPIndex1(string s,string t){
    	int nextval[t.length()],i=0,j=0;
    	GetNextval(t,nextval);
    	while (i<s.length()&&j<int(t.length())){
    		if (j==-1||s[i]==t[j]){	
    			++i;
                ++j;	
    		}
    		else j=nextval[j];
    	}
    	if (j>=t.length())  return i-t.length();
    	else    return -1;
    }
    int strStr(string haystack, string needle){
        if (needle.length()==0)return 0;
        return KMPIndex1(haystack,needle);
    }
};

本题采用的是数据结构KMP算法配图详解(超详细)中的改进KMP算法,讲得很好很详细,码了码了。这道题难度虽然是简单,但是用暴力法或者哈希法求解当然简单了,可是人简单了电脑可就难了,能拿出简单易计算,时间复杂度还是O(M+N)的算法才是难处,能理解KMP“滑动窗口”“最长相同前后缀”这些想法才是难处中的难处。虽然KMP算法需要使用一个和模式串相同长度的串,但是用少量的空间换来搜索时间的飞跃是相当划算的。
记得大二上数据结构的时候老师讲过,说可以用到搜索引擎的字符串匹配上,当时听得人都傻了,不过一般搜索,尤其是汉字搜索很少会有相同前后缀,估计用得不太广。

上一篇:模拟实现strstr


下一篇:php字符串函数的使用