字符串|28. 实现 strStr() 、459.重复的子字符串
28. 实现 strStr()
自己审题思路
这道题刚开始只能想到暴力解法
代码（暴力解法1）：
class Solution {
public:
int strStr(string haystack, string needle) {
int n = haystack.size(), m = needle.size();
for (int i = 0; i + m <= n; i++) {
bool flag = true;
for (int j = 0; j < m; j++) {
if (haystack[i + j] != needle[j]) {
flag = false;
break;
}
}
if (flag) {
return i;
}
}
return -1;
}
};
代码（暴力解法2）：
class Solution {
public:
int strStr(string s, string p) {
int n = s.size(), m = p.size();
for(int i = 0; i <= n - m; i++){
int j = i, k = 0;
while(k < m && s[j] == p[k]){
j++;
k++;
}
if(k == m) return i;
}
return -1;
}
};
看完代码随想录题解后的收获
了解了KMP算法，难点在于next数组的建立。将next数组的建立理解为前缀和后缀的匹配过程，next数组的构建的代码会好些出来一些。
代码（自己完成）：
class Solution {
public:
void getNext(string& pattern, vector<int>& next) {
int j = 0;
next[0] = 0;
for (int i = 1; i < pattern.size(); i++) {
while(j > 0 && pattern[j] != pattern[i]) {
j = next[j -1];
}
if (pattern[j] == pattern[i]) j++;
next[i] = j;
}
}
int strStr(string& haystack, string& needle) {
vector<int> next(needle.size(), 0);
getNext(needle, next);
int j = 0;
int match = 0;
int i = 0;
while (i < haystack.size()) {
while(j > 0 && needle[j] != haystack[i]) {
j = next[j - 1];
}
if (j == 0 && needle[j] != haystack[i]) i++;
match = i - j;
while (needle[j] == haystack[i]) {
j++;
i++;
if (j == needle.size()) return match;
}
}
return -1;
}
};
next直接用数组就好
代码（代码随想录）
class Solution {
public:
void getNext(int* next, const string& s) {
int j = 0;
next[0] = 0;
for(int i = 1; i < s.size(); i++) {
while (j > 0 && s[i] != s[j]) {
j = next[j - 1];
}
if (s[i] == s[j]) {
j++;
}
next[i] = j;
}
}
int strStr(string haystack, string needle) {
if (needle.size() == 0) {
return 0;
}
int next[needle.size()];
getNext(next, needle);
int j = 0;
for (int i = 0; i < haystack.size(); i++) {
while(j > 0 && haystack[i] != needle[j]) {
j = next[j - 1];
}
if (haystack[i] == needle[j]) {
j++;
}
if (j == needle.size() ) {
return (i - needle.size() + 1);
}
}
return -1;
}
};
参考详解
459.重复的子字符串
自己审题思路
暴力解法，一个for循环用来选取子串，一个for循环用子串拼接字符串
代码
class Solution {
public:
bool repeatedSubstringPattern(string s) {
if(s.size()==1) return false;
string temp="",str="";
for(int i=0;i<s.size()/2;++i)
{
temp+=s[i];
while(str.size()<=s.size())
{
str+=temp;
if(str.compare(s)==0)
{
return true;
}
}
str="";
}
return false;
}
};
看完代码随想录题解后的收获
1、 移动匹配
判断字符串s是否由重复子串组成，只要两个s拼接在一起，里面还出现一个s的话，就说明是由重复子串组成。
2、KMP
在由重复子串组成的字符串中，最长相等前后缀不包含的子串就是最小重复子串
代码（移动匹配）
class Solution {
public:
bool repeatedSubstringPattern(string s) {
if(s.size()==1) return false;
string temp="",str="";
for(int i=0;i<s.size()/2;++i)
{
temp+=s[i];
while(str.size()<=s.size())
{
str+=temp;
if(str.compare(s)==0)
{
return true;
}
}
str="";
}
return false;
}
};
代码（KMP）
class Solution {
public:
void getNext (int* next, const string& s){
next[0] = 0;
int j = 0;
for(int i = 1;i < s.size(); i++){
while(j > 0 && s[i] != s[j]) {
j = next[j - 1];
}
if(s[i] == s[j]) {
j++;
}
next[i] = j;
}
}
bool repeatedSubstringPattern (string s) {
if (s.size() == 0) {
return false;
}
int next[s.size()];
getNext(next, s);
int len = s.size();
if (next[len - 1] != 0 && len % (len - (next[len - 1] )) == 0) {
return true;
}
return false;
}
};
参考详解
今日感悟
KMP算法next数组的求解涉及到动态规划，理解了这点KMP算法就比较好写了。
