next数组计算原理是什么

next数组是用来记录模式串中每个位置前缀和后缀相同的最大长度（即最长公共前后缀长度）的数组。计算原理是通过模式串自身的匹配规律来确定，具体步骤如下：

1. 初始化next数组，将next[0]赋值为-1，next[1]赋值为0。

2. 从第2个位置开始，依次计算每个位置的next值，即找到前缀和后缀相同的最大长度。

3. 假设当前位置为i，前缀结束位置为j，初始时j=next[i-1]。

4. 如果模式串的第j+1个字符和第i个字符相同，则next[i]=j+1。

5. 如果模式串的第j+1个字符和第i个字符不同，就继续向前寻找前缀和后缀相同的最大长度，即将j更新为next[j]，直到找到相同的字符或j=-1为止。

6. 如果最终找到相同的字符，则next[i]=next[j]+1，否则next[i]=0。

7. 重复步骤3~6，直到计算出整个next数组。

通过这种方法计算出的next数组可以在KMP算法中用来加速匹配过程，使得匹配时间复杂度降为O(m+n)，其中m为模式串长度，n为文本串长度。

相关问题

KMP算法中的next数组原理是什么

### 回答1：
KMP算法中的next数组原理是通过模式串自身的匹配信息，来确定在匹配失败时，模式串应该向右移动多少位，以便尽可能地减少匹配次数。具体来说，next数组中的每个元素表示模式串中当前字符之前的子串中，最长的既是前缀又是后缀的字符串的长度。在匹配过程中，当模式串的某个字符与文本串的某个字符不匹配时，就可以利用next数组中的信息，将模式串向右移动尽可能少的位数，以便尽快找到下一个可能匹配的位置。这样就可以大大提高匹配效率，避免不必要的重复匹配。

### 回答2：
KMP算法中的next数组是用来存储模式串中每个字符前面的最长公共前缀和最长公共后缀的长度。它的主要作用是在模式串匹配过程中，当出现匹配失败时，通过next数组中存储的信息，来确定下一次匹配的起始位置，避免不必要的回溯。

具体的原理如下：首先，我们需要对模式串进行预处理，得到next数组。开始时，next数组的第一个元素next[0]为-1，第二个元素next[1]为0。然后，从第三个元素开始依次计算next[i]的值。

假设已经计算得到了next[0]~next[i-1]的值，现在需要计算next[i]。比较模式串的前缀和后缀，如果它们的前缀和后缀相同，那么next[i]的值就是该相同前缀的长度加1。如果不相同，则需要继续寻找更短的相同前缀和后缀。通过不断地回溯，直到找到相同的前缀和后缀，或者回溯到模式串的开头，此时next[i]的值为0。

在实际匹配时，当出现匹配失败时，可以根据next数组的值，来确定将模式串右移多少个位置，从而找到下一次匹配的起始位置。相较于暴力搜索的方法，KMP算法利用了已经匹配过的信息，减少了回溯的次数，提高了匹配效率。

通过next数组，KMP算法在O(n+m)的时间复杂度内完成匹配操作，其中n为主串的长度，m为模式串的长度，相较于朴素的字符串匹配算法的时间复杂度O(n*m)，提供了明显的优化。

### 回答3：
KMP算法是一种字符串匹配算法，用于在一个主串中查找子串。而KMP算法中的核心思想是通过预处理模式串（子串）构建一个next数组，用于指导匹配过程中的模式串移动操作。

next数组存储的是模式串中每个位置的最长公共前后缀的长度。这样，在匹配过程中，当发生不匹配时，我们可以根据next数组中的值来决定移动模式串的位置。

具体的next数组构建过程如下：
1. 初始化next数组，第一个元素next[0]为-1。
2. 从模式串的第二个字符开始遍历至最后一个字符，计算每个位置i的next[i]的值。
a. 若模式串的前缀和后缀的最长公共前后缀长度为k，在位置i的字符匹配失败之后，可以将模式串移动的位置设置为k，继续下一轮的匹配。
b. 若位置i之前的最长公共前后缀长度为k，而第i个字符不匹配，则根据next[k]的值来更新当前位置i的next[i]值，即next[i] = next[k]。
c. 若位置i之前的最长公共前后缀长度为k，而第i个字符匹配成功，则当前位置i的next[i]值为k+1。
d. 重复上述步骤，直至计算完成所有位置的next值。

通过构建好的next数组，可以在匹配过程中根据当前字符不匹配时的next值来决定模式串的移动位置，从而实现快速的字符串匹配。

总结来说，KMP算法中的next数组原理即模式串的最长公共前后缀长度，用于指导匹配过程中的模式串移动操作，提高了算法的效率。

ConcurrentHashMap 底层具体实现知道吗？实现原理是什么？

ConcurrentHashMap是JDK提供的一个线程安全的哈希表实现。它的底层实现采用了分段锁（Segment）的方式。

简单来说，ConcurrentHashMap将哈希表分成了多个Segment，每个Segment维护了一个哈希表的子集。在读取操作时，ConcurrentHashMap只需要获取对应Segment的读锁，而在写入操作时，只需要获取对应Segment的写锁，这样可以大大提高并发性能。

具体实现原理如下：

1. ConcurrentHashMap内部有一个Segment数组，默认大小为16，所以最多可以支持16个线程并发修改。

2. 每个Segment里面维护了一个HashEntry数组，HashEntry中包含了key、value和next指针，next指针用于解决哈希冲突。

3. 写入操作时，首先根据key计算出对应的Segment，然后获取该Segment的写锁，再根据key计算出在该Segment中的位置，如果该位置为空，则直接插入，否则遍历链表，如果找到相同的key，则更新其value，否则在链表头插入新的节点。

4. 读取操作时，根据key计算出对应的Segment，然后获取该Segment的读锁，再根据key计算出在该Segment中的位置，遍历链表查找对应的节点，如果找到则返回其value，否则返回null。

总之，ConcurrentHashMap的并发性能非常优秀，它通过将一个大的锁分成多个小的锁，实现了高效的并发控制。