1.实现strstr()
class Solution {
public:
int strStr(string s, string p) {
if(p.empty()) return 0;
int m=p.size(),n=s.size();
vector<int>ne(m+1);
s=' '+s,p=' '+p;
for(int i=2,j=0;i<=m;i++)
{
while(j && p[i]!=p[j+1]) j=ne[j];
if(p[i]==p[j+1]) j++;
ne[i]=j;
}
for(int i=1,j=0;i<=n;i++)
{
while(j && s[i]!=p[j+1]) j=ne[j];
if(s[i]==p[j+1]) j++;
if(j==m) return i-m;
}
return -1;
}
};
2.459 重复的数字
class Solution {
public:
bool repeatedSubstringPattern(string s) {
int n=s.size();
vector<int>ne(n+1);
s=' '+s;
for(int i=2,j=0;i<=n;i++)
{
while(j && s[i]!=s[j+1]) j=ne[j];
if(s[i]==s[j+1]) j++;
ne[i]=j;
}
int t=n-ne[n];
return t<n && n%t==0;
}
};