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的相关知识点如果有不懂的，可以看下这篇博客有详细讲解:
解法三:哈希加速暴力
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; }
