设目标串为s="abcaabbcaaabababaabca",模式串为t="babab"。 计算模式t的nextval函数值
时间: 2024-06-05 12:10:46 浏览: 6
首先,计算t的next数组:
b a b a b
0 0 1 2 3
对于nextval数组,它是在next数组的基础上计算得出的。其主要思想是当t[j]!=t[next[j]]时,如果t[next[j]]等于t[i],则nextval[i]=next[j],否则继续递归找到一个满足条件的next[j]为止。
因此,我们从后往前遍历t数组,计算出nextval数组:
b a b a b
0 0 1 2 3
当j=4时,t[j]!=t[next[j]],因此继续递归,找到next[j]=1,此时t[next[j]]=a,但是a!=t[i]=4,因此继续递归,找到next[j]=0,此时t[next[j]]=b,且b=t[i],因此nextval[i]=next[j]=0。
当j=3时,t[j]!=t[next[j]],因此继续递归,找到next[j]=1,此时t[next[j]]=a,但是a!=t[i]=3,因此继续递归,找到next[j]=0,此时t[next[j]]=b,且b=t[i],因此nextval[i]=next[j]=0。
当j=2时,t[j]!=t[next[j]],因此继续递归,找到next[j]=1,此时t[next[j]]=a,但是a!=t[i]=2,因此继续递归,找到next[j]=0,此时t[next[j]]=b,且b=t[i],因此nextval[i]=next[j]=0。
当j=1时,t[j]!=t[next[j]],因此继续递归,找到next[j]=0,此时t[next[j]]=b,但是b!=t[i]=1,因此继续递归,找到next[j]=-1,此时nextval[i]=-1。
当j=0时,t[j]!=t[next[j]],因此继续递归,找到next[j]=-1,此时nextval[i]=-1。
因此,模式t的nextval函数值为[-1, 0, 0, 0, 1]。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![gz](https://img-home.csdnimg.cn/images/20210720083447.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![whl](https://img-home.csdnimg.cn/images/20210720083646.png)
![gz](https://img-home.csdnimg.cn/images/20210720083447.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![whl](https://img-home.csdnimg.cn/images/20210720083646.png)