模板
// pi代表前缀函数
// pi[i]: s[0~i]的最长匹配真前后缀长度
vecotr<int> pi(str.size());
// 求前缀函数
for(int i=1; i<str.size(); i++){
int len=pi[i-1]; //前一个值的pi len是我们想要找到的一个长度值
while(len!=0&&str[i]!=str[len]){ // 不匹配时,求次小的前缀函数
len=pi[len-1];
}
if(str[i]==str[len]){
p[i]=len+1;
}
}
简单应用
#
的作用是避免找到的字符串由模板串和待查找串两部分构成
int strStr(string s, string pattern) {
int n=s.size();
int m=pattern.size();
// # 的作用,避免找到的匹配字符串是由pattern的部分+s的一部分共同构成的
string str=pattern+"#"+s;
vector<int> pi(str.size()); // 前缀数组,最长匹配真前后缀长度
for(int i=1; i<str.size(); i++){
int len=pi[i-1];
while(len!=0&&str[i]!=str[len]){
len=pi[len-1];
}
if(str[i]==str[len]){
pi[i]=len+1;
if(pi[i]==m)
return i-2*m;
}
}
return -1;
}
标签:string,int,pattern,算法,kmp,pi,模板,size
From: https://www.cnblogs.com/Biang-blog/p/18346848