深入理解KMP算法中的next数组：北大OJ2406题解

### 深入理解KMP算法中的next数组

#### 1. 未改良的next数组

在KMP算法中，未改良的next数组用于记录模式串的部分匹配值。具体来说，`next[j] = k` 表示在模式串 `str` 中，`str[0...k-1]` 和 `str[j-k...j-1]` 是相同的。这里 `k` 的含义是当当前字符不匹配时，应该从 `str[k]` 开始下一次检查。

例如，对于字符串 `aaaa`，`next[3] = 2`，表示如果第四个字符不匹配，则应从第二个字符开始重新匹配。

对于给定的字符串，若其长度为 `len`，则 `next[len]` 可以用来判断是否存在最小循环单元。具体而言，如果 `len % (len - next[len]) == 0`，则存在最小循环单元，且该单元长度为 `len - next[len]`。否则，不存在最小循环单元。

- 如果找不到任何循环单元（如 `aaab`），返回值为 `0`，此时也可以整除，结果为 `1`。
- 如果可以找到循环单元（如 `aabaa`），返回值为 `2`，无法整除。

#### 2. 改良的next数组

改良后的next数组在构建过程中考虑了 `str[k]` 和 `str[j]` 是否相等。如果相等，则 `next[j] = next[k]`。这种改进可以避免不必要的重复计算，提高算法效率。

### 示例代码

以下是C++实现的KMP算法，包括next数组的构建和最小循环单元的判断：

```cpp
#include
#include
#include
#include
using namespace std;

void get_next(char str[], int next[], int len) {
next[0] = -1;
int k = -1, j = 0;
while (j if (k == -1 || str[k] == str[j]) {
k++; j++;
next[j] = k;
} else {
k = next[k];
}
}
}

int main() {
char str[1000000];
while (scanf("%s", str) != EOF && str[0] != '.') {
int len = strlen(str);
int next[len + 1];
for (int i = 0; i <= len; i++)
next[i] = 0;
get_next(str, next, len);
int n = next[len];
if (n != 0 && len % (len - n) == 0)
printf("%d\n", len / (len - n));
else
printf("1\n");
}
return 0;
}
```

通过上述代码，我们可以高效地解决字符串匹配问题，并准确判断是否存在最小循环单元。希望这篇文章能帮助你更好地理解KMP算法及其应用。