next数组求解详解,求next数组的两种方法
Yyds干货库存
作者:云晓艺
个人主页:云小易主页。
代码:云小易(yunxiaoyi003)-Gitee.com
座右铭:你要敢于默默面对自己。强大才是核心。不要等到什么都没有了才下定决心去做。种一棵树最好的时间是十年前,其次是现在!学会和解自己,与过去和解,试着爱自己。希望在春天到来之前,我们一起面朝大海,春暖花开!
专栏:C语言初级阶段的日常杂记
求下一个字符串数组:方法一:这里我们把下一个数组的第1位和第2位分别设为0,1(或者-1,0,这里先设为0,1,必要的话减一)
后面求解每一位的下一个值时,按照前一位进行比较。
从第三位开始,比较对应于其下一个值的前一位的内容,
如果相等,则该位的下一个值是前一位的下一个值加1;
如果不是,则继续寻找对应于下一个值的内容以与前一位进行比较,
直到发现对应于一个比特上的内容的下一个值的内容等于前一个比特,
那么这个位加1对应的值就是需求的下一个值;
如果找到了第一位,但没有找到与前一位相等的内容,则已求解位的下一个值为1。
总结:如果相等,加一。如果你不平等,向前看。找到一个就加一个。如果你找不到一个,你就是一个。
方法二:1。首先,找出前缀和后缀的最长公共元素长度。术语“前缀和后缀的最长公共元素长度”可能很难理解。稍安勿躁,且听本公子(* *):
编辑
(请多注意,三联,自己创作(*)画不容易)
编辑
2.将每个对应前缀和后缀的最长公共元素长度整体后移一位,第一位设置为-1。获取它的下一个数组(第一和第二位-1,0)
完整代码:# define _ CRT _ secure _ no _ warnings 1
#包含stdio.h
#包含stdlib.h
#包含字符串. h
Void prefix _ table (char pattern [],int prefix [],int n)//查找下一个数组
{
前缀[0]=0;
int len=0;
int I=1;
当(名词)
{
if(模式[i]==模式[len])
{
len
前缀[I]=len;
我;
}
其他
{
if (len 0)
{
len=前缀[I];
}
其他
{
前缀[I]=len;
我;
}
}
}
}
void Move _ prefix _ table(int prefix[],int n)//向后移动下一个数组
{
int I;
for(I=n-1;我我-)
前缀[i]=前缀[I-1];
前缀[0]=-1;
}
int main(void)
{
char pattern[]= ABABCABAA ;
int n=9;
int前缀[9]={ 0 };
prefix_table(模式,前缀,n);
move _前缀_表(前缀,n);
int I;
for(I=0;我我)
{
printf(%d ,前缀[I]);
}
返回0;
}
郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。