算法笔记(一）—— KMP算法练习题
目录
1.实现strStr
2. 重复的子字符串
1.实现strStr
解法一:暴力匹配(BF)算法
int strStr(char * haystack, char * needle){assert(haystack!=NULL&&needle!=NULL);int len1=strlen(haystack);int len2=strlen(needle);int i=0,j=0;if(len2==0){return 0;}if(len1==0&&len2!=0){return -1;}while(i<len1&&j<len2){if(haystack[i]==needle[j]){i++;j++;}else{i=i-j+1;j=0;}}if(j>=len2){return i-j;}else{return -1;}
}解法二:KMP算法
int strStr(char * haystack, char * needle){if(needle[0]=='\0')return 0;int len1=(int)strlen(haystack);int len2=(int)strlen(needle);int i=0;int j=0;int ans=-1;int* next=(int*)malloc(sizeof(int)*len2);getnext(next,needle);while(i<len1){if(j==-1||haystack[i]==needle[j]){++i;++j;}else{j=next[j];}if(j==len2){ans=i-len2;break;}}return ans;
}
void getnext(int next[],char* needle)
{next[0]=-1;int j=0;int k=-1;int len=(int)strlen(needle);while(j<len-1){if(k==-1||needle[j]==needle[k]){++j;++k;next[j]=k;}else{k=next[k];}}}解法1和解法2的相关知识点如果有不懂的，可以看下这篇博客有详细讲解:
>>>KMP算法详解
解法三:哈希加速暴力
class Solution {
public:int strStr(string haystack, string needle) {if(needle=="") return 0;int n = haystack.size(), m = needle.size();int hash = 0;for(auto c: needle){hash += c -'a';}int cur = 0;for(int i = 0; i < n; i++){cur += haystack[i] - 'a';if(i >= m ) cur -= haystack[i-m] - 'a';if(i >= m-1 && cur == hash && haystack.substr(i-m+1,m) == needle)return i-m+1;}return -1;}
};解法四:
解题思路
1.定义两个指针，头指针从haystack数组的头开始，尾指针的位置由needle数组的长度确定，也就是(0+len2-1)
2.进入while循环，循环结束的条件是尾指针到达haystack数组的尾部
3.判断haystack数组以head为开头，len2为长度的子串和needle数组是否相同，是则返回此时的head值
4.对头尾两个指针做++操作，保持窗口大小
5.循环结束，代表匹配失败，返回-1
class Solution {
public:int strStr(string haystack, string needle) {int len1=haystack.size(),len2=needle.size();//尾指针的位置由needle数组的长度确定，也就是(0+len2-1)int head=0,tail=len2-1;//循环结束的条件是尾指针到达haystack数组的尾部while(tail<len1){//判断haystack数组以head为开头，len2为长度的子串和needle数组是否相同if(haystack.substr(head,len2)==needle) return head;head++;tail++;}return -1;}
};
解法五：C++库函数的运用
class Solution {
class Solution {
public:int strStr(string haystack, string needle) {if(needle.empty())return 0;int pos=haystack.find(needle);return pos;}
};本题应该还有很多解法，有想到的伙伴们可以评论区留言共同讨论.
2. 重复的子字符串
解法一:KMP算法
以下是我在力扣发现的一种比较好理解的KMP解法
Next数组不减一，不移动的做法
注释详细请看代码
强烈建议大家把next数组打印出来，看看next数组里的规律，有助于理解KMP算法
最后的if判断可以这样理解：
如果答案是 true 的话，next 表前几位（子字符串）都是 0，后边将是一直递增，next（n－1）存放的就是原字符串减去子字符串长度的值 ，记为len2，将 len－len2的值记为len1，len1它就是子字符串的长度，一定是可以被 len 整除的！
//求字符串s的next数组
void Getnext(int *next, char *s, int len)
{int j=0;next[0]=0;for(int i=1; i<len; i++){while(j>0 && s[i]!=s[j]){j=next[j-1];}if(s[i] == s[j]){j++;}next[i]=j;}
}bool repeatedSubstringPattern(char * s)
{int len = strlen(s);if(len == 0) return false;int *next = (int*)malloc(sizeof(int) * len);Getnext(next, s, len);// next[len-1]!=0 代表s字符串有最长的相等前后缀// len % (len - next[len-1]) == 0 // 代表（数组长度 - 最长相等前后缀的长度）正好可以被数组的长度整除if(next[len-1]!=0 && len % (len - next[len-1]) == 0){return true;}return false;
}解法二:枚举法
思路与算法
如果一个长度为 nn 的字符串 ss 可以由它的一个长度为 n'n 的子串 s's ′重复多次构成，那么：nn 一定是 n'n ′ 的倍数；s's ′一定是 ss 的前缀；对于任意的 i \in [n', n)i∈[n ′ ,n)，有 s[i] = s[i-n']s[i]=s[i−n ′ ]。也就是说，ss 中长度为 n'n ′ 的前缀就是 s's ′ ，并且在这之后的每一个位置上的字符 s[i]s[i]，都需要与它之前的第 n'n ′ 个字符 s[i-n']s[i−n ′ ] 相同。因此，我们可以从小到大枚举 n'n ′ ，并对字符串 ss 进行遍历，进行上述的判断。注意到一个小优化是，因为子串至少需要重复一次，所以 n'n ′ 不会大于 nn 的一半，我们只需要在 [1, \frac{n}{2}][1, 2n ] 的范围内枚举 n'n ′即可。
bool repeatedSubstringPattern(char * s){int len=strlen(s);for(int i=1;i*2<=len;i++){if(len%i==0){bool match=true;for(int j=i;j<len;j++){if(s[j]==s[j-i]){match=true;}else{match=false;break;}}if(match==true){return true;}}}return false;
}解法三:字符串匹配
bool repeatedSubstringPattern(char* s) {int n = strlen(s);char k[2 * n + 1];k[0] = 0;strcat(k, s);strcat(k, s);return strstr(k + 1, s) - k != n;
}