28. 实现 strStr()
用了双指针的方法写了出来,需要注意的一点是：我本以为如果找到了配对，那应该是temp_i-n_length+1；但其实不用加一。因为在前面的for loop里，尽管j大于n_length之后就退出了，但是temp_i还是加上了最后一次1才退出loop的。
class Solution {
public:
int strStr(string haystack, string needle) {
int n_length = needle.length();
int h_length = haystack.length();
for(int i=0; i<=(h_length-n_length); i++){
if(haystack[i] == needle[0]){
int temp_i = i;
int count_same = 0;
for(int j=0; j<n_length; j++){
if(haystack[temp_i] != needle[j]){
break;
}
else{
count_same++;
}
temp_i++;
}
if(count_same == n_length){
return temp_i-n_length;
}
else{
i = temp_i - count_same;
}
}
}
return -1;
}
};
459.重复的子字符串
写的稀里糊涂，还没写对。问题是没找到一个合适的function，去检测特定range里有没有该substr。
class Solution {
public:
bool repeatedSubstringPattern(string s) {
int cur_sub_len = 1;
int s_length = s.length();
while(cur_sub_len <= (s_length/2)){
if((s_length%cur_sub_len) == 0){
string cur_sub = s.substr(0,cur_sub_len);
int pos = 0;
int count_sub = 0;
for(int i=0; i<s_length; ){
if(s.find(cur_sub,i, i+cur_sub_len)){
count_sub++;
i = i + cur_sub_len;
}
else{
break;
}
cout<<cur_sub<<" "<<i<<endl;
}
if(count_sub == (s_length/cur_sub_len)){
return true;
}
}
cur_sub_len++;
}
return false;
}
};
最后看着答案，写出来了。
class Solution {
public:
bool repeatedSubstringPattern(string s) {
int n = s.size();
for (int i = 1; i * 2 <= n; ++i) {
if (n % i == 0) {
bool match = true;
for (int j = i; j < n; ++j) {
if (s[j] != s[j % i]) {
match = false;
break;
}
}
if (match) {
return true;
}
}
}
return false;
}
};
