kmp算法
kmp算法总体来说分为两步:
1、next数组求解
根据下边的子函数GetNext()来理解,其中,最难理解的为j = next[j]这一步,如下图,两个||表示最长的匹配好的前缀和后缀,那么接下来,这个父串中后缀直接和子串的前缀进行匹配好了(就是一个等价关系:父前缀=子前缀=父后缀=子后缀),只需要比较父串当前位置和子串中最长前缀的下一位即可,而这个下一位就是next[j]。
确实难懂啊!!!!我也是琢磨了好久才明白的,发明这些算法的,简直他妈就是变态!!!!
2、kmp查找
这个逼就好理解多了,不做多解释,下面贴代码
#include<bits/stdc++.h>
using namespace std;
void PrintArr(int *p, int len)
{
for (int i = 0; i < len; i++)
cout << p[i] << " ";
cout << endl;
}
void GetNext(string a,int *next,int len)
{
int i = 0;
int j = -1;
next[0] = -1;
while (i < len)
{
if (j == -1 || a[i] == a[j])
{
++i;
++j;
next[i] = j;
}
else
{
j = next[j];
}
}
}
void KmpFind(string s1, string s2, int *next)
{
int len1 = strlen(s1.c_str());
int len2 = strlen(s2.c_str());
int i = 0;
int j = 0;
while (i < len1 && j < len2)
{
if (j == -1 || s1[i] == s2[j])
{
++i;
++j;
}
else
{
j = next[j];
}
}
if (j == len2)
{
cout << "子串在父串中第一次出现的位置:" << i - j + 1 << endl;
}
else
{
cout << "子串不在父串中" << endl;
}
}
int main()
{
string a = "ababaaaba";
string b = "abcadbaababaaabababc";
int len = strlen(a.c_str());
//cout << sizeof(a) << endl;
int *next = (int *)malloc(len * sizeof(int));
GetNext(a, next, strlen(a.c_str()));
PrintArr(next,len);
KmpFind(b, a, next);
system("pause");
return 0;
}
i画船听雨: 还有switch
123123123LWQ: 大佬就是大佬,佩服
123123123LWQ: 就这 ?????????????????大佬牛逼!
123123123LWQ: 就这?????
weixin_44738999: 大佬就是大佬,佩服