建企业网站价格_山西并州建设有限公司_广州seo网络培训课程_百度统计手机app

1.重复的子字符串

class Solution {
public:void getNext(vector<int> &next,const string s){int j=0;next[j]=0;for(int i=1;i<s.size();i++){while(j-1>=0&&s[i]!=s[j]){j=next[j-1];}if(s[i]==s[j]){j++;next[i]=j;}else{next[i]=0;}}}bool repeatedSubstringPattern(string s) {vector<int> next(s.size(),0);getNext(next,s);int maxindenext = next[s.size()-1];return maxindenext!=0&&s.size()%(s.size()-maxindenext)==0;}
};

2.找出字符串中第一个匹配项的下标

思路：先确定needlenext数组 然后遍历next 如果当前元素和needle【j】 相等 继续遍历 不等循环回退j=next[j-1];再次判断是否相等 不相等继续回退到j=0相等的话直接j++;

            while(j-1>=0&&haystack[i]!=needle[j]){j = next[j-1];}if(haystack[i] == needle[j]){j++;}

完整代码

class Solution {void getNext(vector<int > & next, string needle){int j=0;next[j]=0;for(int i=1;i<needle.size();i++){while(j-1>=0&&needle[i]!=needle[j]){j = next[j-1];}if(needle[i]==needle[j]){j++;}next[i]=j;}} public:int strStr(string haystack, string needle) {vector<int > next(needle.size(),0);getNext(next,needle);int j =0;for(int i=0;i<haystack.size();i++){while(j-1>=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;}
};