str表示文本串,m表示模式串;
str[i] 和 m[j] 是正在进行匹配比较的字符;
KMP的时间复杂度是O(m+n) , 暴力求解的时间复杂度是O(m*n)
KMP利用了m[ 0 : j-1 ]和str[ i-j : i-1 ]是相同的这一点,而暴力求解显然做不到.
int kmp(string str,string m)
{
int next[MAXN];
next[0] = -1;
int i=0;
int j=-1;
while(i<m.size())
{
if(j==-1 || m[i]==m[j])
{
i++;
j++;
next[i] = j;
}
else
{
j = next[j];
}
}
i=0;
j=0;
while(i<str.size() && j<m.size())
{
if(j==-1 || str[i]==m[j])
{
i++;
j++;
}
else
{
j =next[j];
}
if(j==m.size()-1)
{
return i-j;
}
}
return -1;
}
