KMP算法和原来的暴力匹配算法解析
有一个文本字符串s，和一个模式串p，想要查找s中是否包含p，以及s中p出现的第一个位置。
首先用暴力匹配，主要是不相等的时候就回溯，这样时间复杂度较高。
核心思想i和j分别指向s和p，如果s[i] == p[j] {i++,j++,count++}
如果count == p.size()就说明找到了；如果s[i] != p[i]，此时回溯，i = i-j+1;j=0;
代码如下：
int findStrWithoutKMP(string s,string p)
{
if(s.size() == 0 || p.size() == 0 || s.size() < p.size()) return -1; //表示不存在 s的长度要大于等于p
int i =0;
int j =0;
int curLen = 0;
while (i>=0 && i<s.size())
{
//cout<<"This i is "<<i<<" j is "<<j<<endl;
curLen = 0;
for(int j=0;j<p.size();) //j++不需要在这里+
{
if(s[i] == p[j] && i<s.size() && j<p.size()) //加上 i<s.size()和j<p.size这个判断和快速排序left right判断一个道理
{
curLen++;
//cout<<"This i is "<<i<<" j is "<<j<<" This curLen is "<<curLen<<endl;
if(curLen == p.size()) //先进行curLen判断 再进行i++和j++
{
return (i-p.size()+1) + 1; //i-p.size()+1是从0开始的位置 等于2表示是0 1 2位置所以从1开始实际是第3个，所以再加个1
}
i++;
j++;
} else
{
i = i-j+1;
j = 0;
break;
}
}
}
return -1;
} 下面再说先kmp算法，kmp算法核心就是利用next数组，是的文本串s不回溯，一直向前，模式串p根据next数组来回溯到对应的位置。 next数组的求法和kmp主函数的有一定类似。这个kmp函数返回的是s中所有包括p的位置，可能有多个，位置从0开始。主要代码如下：
vector<int> next(string s)
{
vector<int> res(s.size(),0);
if(s.size() == 0) return res;
int count = 0;
for(int i=1;i<s.size();i++)
{
while (count > 0 && s[i] != s[count])
{
count = res[count -1];
}
if(s[i] == s[count])
{
count++;
}
res[i] = count;
}
return res;
}
//00011212001212000
//string s = "abcaababdfababfds";
//string p = "abab";
//int findIndexStr(string )
vector<int> searchByKMP(string s,string p)
{
vector<int> positions;
vector<int> nextVector = next(s); //这个vector命名居然不能和原来的一样
/************************************
for(int i=0;i<nextVector.size();i++)
{
cout<<nextVector[i]<<" ";
}
cout<<endl;
************************************/
int count = 0;
for(int i=0;i<s.size();i++)
{
while (count > 0 && p[count] != s[i])
{
count = nextVector[count-1];
}
if(p[count] == s[i])
{
count++;
}
if(count == p.size())
{
positions.push_back(i - p.size()+1);
count = nextVector[count-1]; //关键这一行是为啥
}
}
return positions;
} 
投递理想汽车等公司10个岗位 >
