已知模式串求next数组
时间: 2023-10-10 08:16:08 浏览: 40
next数组是用于KMP算法的,可以用于快速匹配模式串和文本串。next数组表示模式串中每个字符前面的子串中,最长的相等前缀和后缀的长度。具体求解方法如下:
1. 初始化next数组,next[0]=-1,next[1]=0。
2. i从2开始遍历模式串。
3. 如果模式串中i-1位置的字符与前面的相等字符的后一个字符相等,则next[i]=next[i-1]+1。
4. 如果模式串中i-1位置的字符与前面的相等字符的后一个字符不相等,则需要不断回溯,找到最长的相等前缀和后缀的长度。具体做法是,将i-1位置的字符的前一个字符的next值赋给j,然后在循环中不断回溯,直到找到相等的字符或者回溯到了整个模式串的起始位置。如果找到了相等的字符,就将j+1赋给next[i],否则将next[i]赋为0。
5. 返回next数组。
下面是Python代码实现:
```python
def get_next(pattern):
n = len(pattern)
next = [-1] * n
i, j = 0, -1
while i < n - 1:
if j == -1 or pattern[i] == pattern[j]:
i += 1
j += 1
next[i] = j
else:
j = next[j]
return next
```
其中,i表示模式串中当前要求next值的位置,j表示当前相等前缀和后缀的长度。如果j=-1,表示没有相等前缀和后缀,那么就需要将i和j都向后移动一位。如果pattern[i]==pattern[j],表示当前字符和相等前缀的下一个字符相等,那么就可以将next[i]=j+1。否则,就需要回溯,将j的值更新为next[j],继续寻找相等前缀和后缀。