nextval
刚接触数据结构，对于其中的一些算法都不是很了解，这几天刚在学习串的内容，里面介绍了两种串的模式匹配算法，一种是BF算法（也叫做BoyFriend算法）；另一种是KMP算法（也叫做“看毛片”算法）。BF算法的实现很简单，很暴力，但是在时间复杂度的限制下，这不是一个很好的算法。为了提高程序运行的效率，出现了KMP算法，讲真的，算法真的很难理解（对于大佬来说，这种都是基础的题目，但对于像我样的菜鸡，就是登天啦~~）。这几天通过看视频教程，还有看大佬的博客，也懂的了一些简单的方法。
下面跟大家分享下成果吧~
例子：abaabcac
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 例子 | a | b | a | a | b | c | a | c |
| next | 0 | 1 | 1 | 2 | 2 | 3 | 1 | 2 |
具体步骤：第一位和第二位肯定为0和1
第三位开始比较前面串的最大真子串，没有为1
第四位找：两位的时候 ab和ba 不一样
一位的时候 a 和 a 一样，长度为1，所以next[4]=1+1=2
以此类推。
总结一下：第一位和第二位固定；
其余的位数就看它前面的串，找其中长度最大的真子串（注意：找的时候，找两端，头在一端，尾在一端，
找到的串，从左到右读起来是相同的。比如：ab，ba这两个就不一样。相信聪明的你会一听就明白的），找到next的值为长度加1，未找到值为1。
nextval数组的计算方法呢，有两种：一种是靠直接观察法来算，另一种是依靠next数组来算。第一种没怎么懂，下面讲下用next数组来计算nextval数组的例子吧。
还是上面的例子：
例子：abaabcac
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 例子 | a | b | a | a | b | c | a | c |
| next | 0 | 1 | 1 | 2 | 2 | 3 | 1 | 2 |
| nextval | 0 | 1 | 0 | 2 | 1 | 3 | 0 | 2 |
具体步骤：若前两位相同，则nextval为0，若不同则为1，第二位的b与第一位的a不同，所以为1
第三位的时候next值为1，第三位的a与当前next值所对应的值（即是第一位的a）相同，
所以为0。
第四位的next值为2，2对应的值为b，与当前的值不相同，nextval值为当前的next值，第四位为2
第五位的next值为2，2对应的值为b，相同，继续比，第二位b对应的next值为1,1对应的next值
为a，不同，结束，所以nextval值为1。
以此类推，聪明的你肯定明白这其中的规律的。
总结下规律：第一位的nextval值肯定为0，第二位，观察第一位，相同为0，不同为1。剩下的求nextval：
若当前值与当前next所对应的值不同，则直接为当前next值；若相同，则继续查找对应的next值，有不同的就把对应的next值给nextval（正如上面的第五位查找），否则为0。
呼呼~说了这么多，你明白了吗？
下面贴上代码，供大家检验，对比。
#include<bits/stdc++.h>
using namespace std;
#define maxn 255
typedef struct
{
char ch[maxn+1];
} SString;
void Init(SString &S)
{
char str[maxn];
cin>>str;
S.ch[0] = strlen(str);//用第一个位置，存数组的长度
for(int i=0;str[i];i++)
S.ch[i+1] = str[i];
}
void get_nextval(SString &S1,int nextval[])
{
int i=1,j=0;
nextval[1] = 0;
while(i<S1.ch[0])
{
if(j==0||S1.ch[i]==S1.ch[j])
{
i++;
j++;
if(S1.ch[i]!=S1.ch[j])nextval[i] = j;
else
nextval[i] = nextval[j];
}
else
j = nextval[j];
}
for(int k=1; k<=S1.ch[0]; k++)
cout<<nextval[k]<<' ';
}
void get_next(SString &T,int next[])
{
int i=1,j=0;
next[1] =0;
while(i<T.ch[0])
{
if(j==0||(T.ch[i]==T.ch[j]))
{
++i;++j;
next[i]=j;
}
else
j = next[j];
}
for(int k=1;k<=T.ch[0];k++)
cout<<next[k]<<' ';
}
int main()
{
SString S1;
Init(S1);
int next[maxn];
///Get_next(S1,next);
get_next(S1,next);
cout<<endl;
get_nextval(S1,next);
}
欢迎大佬指教~
文章最后发布于: 2017-10-13 15:16:31
相关阅读
定义数组的三种方式 以 int型 的一维数组为例，说说三种定义方式int[] arr = new int[3]; 这是最常用的方式，定义时就含有默认值，可以
1、首先理解一下“深拷贝”和“浅拷贝”的区别： 浅拷贝：a = b;//a和b中存的是相同的地址，该地址指向堆内存中相同的地方，即a和b就是一
首先，理解一下数组指针和指针数组这两个名词： “数组指针”和“指针数组”，只要在名词中间加上“的”字，就知道中心了—— 数组的指针
string s[]={“S1”,“S2”,“S3”};string s[3]={“S1”,“S2”,“S3”};string s[40]={“S1”,“S2”,“S3”};//下标3及以后的
array_slice($arr,0,3) //获取键值0-3的数组元素更多：http://www.php100.com/cover/php/191.html