KMP中next数组的理解与应用

迷南。 2023-08-17 15:47 108阅读 0赞

## 理解 ##

### 1、next数组一直往前走 ###

next数组一直往前走，得到的所有前缀也是当前主串的后缀，当然了，也是当前主串的前缀。![1365470-20190131122459513-150838350.png][]

### 2、周期性字符串 ###

1、周期性字符串$\\Leftrightarrow n \\,\\% \\, (n-next\[n\]) == 0 \\ \\&\\& \\ next\[n\] \{\\ \} \{\\!\}!\{=\} \\ 0 $，循环节长度是$n-next\[n\]$。

![1365470-20190131124532356-226085080.png][]

2、next数组往前跳的步长是一样的，除了最后一次。即$i-next\[i\]$保持恒定。

![1365470-20190131125339990-1474978713.png][]

## 应用 ##

*  题目一：[Period][]

思路：先求出next数组，然后遍历一遍next数组得到所有字符结尾的字符串循环节的长度及个数

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<cstring>
     3 #include<iostream>
     4 using namespace std;
     5 
     6 const int maxn = 1000000 + 10;
     7 int nexts[maxn],n;
     8 char s[maxn];
     9 
    10 void pre_kmp()
    11 {
    12     int i = 0, j = nexts[0] = -1;
    13     while (i < n)
    14     {
    15         while (j != -1 && s[i] != s[j])  j = nexts[j];    //当前不匹配，j回退，寻找是否存在一个长度较小的字串和开头的字串相等
    16         nexts[++i] = ++j;                //j等于已匹配的长度，如果当前位置也匹配，则nexts直接为j+1
    17     }
    18 }
    19 
    20 void slove()
    21 {
    22     pre_kmp();
    23     for(int i = 2; i <= n; i++)
    24         if (i % (i - nexts[i]) == 0 && nexts[i] != 0)  printf("%d %d\n", i, i / (i - nexts[i]));
    25 }
    26 
    27 int main()
    28 {
    29     int T = 0;
    30     while (scanf("%d",&n) == 1 && n)
    31     {
    32         scanf("%s", s);
    33         s[n] = '#';
    34         if (T)  printf("\n");
    35         printf("Test case #%d\n", ++T);
    36         slove();
    37     }
    38     return 0;
    39 }

*  题目二：[Power Strings][]

思路：先求next数组，再直接求循环节

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<cstring>
     3 #include<iostream>
     4 using namespace std;
     5 
     6 const int maxn = 1000000 + 10;
     7 int nexts[maxn],n;
     8 char s[maxn];
     9 
    10 void pre_kmp()
    11 {
    12     int i = 0, j = nexts[0] = -1;
    13     //int n = strlen(s);
    14     while (i < n)
    15     {
    16         while (j != -1 && s[i] != s[j])  j = nexts[j];    //当前不匹配，j回退，寻找是否存在一个长度较小的字串和开头的字串相等
    17         nexts[++i] = ++j;                //j等于已匹配的长度，如果当前位置也匹配，则nexts直接为j+1
    18     }
    19 }
    20 
    21 void slove()
    22 {
    23     pre_kmp();
    24     if (n % (n - nexts[n]) != 0)  printf("1\n");
    25     else  printf("%d\n", n / (n - nexts[n]));
    26 }
    27 
    28 int main()
    29 {
    30     int T = 0;
    31     while (scanf("%s", s) == 1 && s[0] != '.')
    32     {
    33         n = strlen(s);
    34         s[n] = '#'; 
    35         slove();
    36     }
    37     return 0;
    38 }

*  题目三：[Count The String][]

思路：求所有前缀出现的次数和，由于next数组回退得到的前缀也是主串的后缀，所以所有next回退的次数加上本身的一次取模就是答案。

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<cstring>
     3 #include<iostream>
     4 using namespace std;
     5 
     6 const int mod = 10007;
     7 const int maxn = 200000 + 10;
     8 int nexts[maxn], n;
     9 char s[maxn];
    10 
    11 void pre_kmp()
    12 {
    13     int i = 0, j = nexts[0] = -1;
    14     //int n = strlen(s);
    15     while (i < n)
    16     {
    17         while (j != -1 && s[i] != s[j])  j = nexts[j];    //当前不匹配，j回退，寻找是否存在一个长度较小的字串和开头的字串相等
    18         nexts[++i] = ++j;                //j等于已匹配的长度，如果当前位置也匹配，则nexts直接为j+1
    19     }
    20 }
    21 
    22 void slove()
    23 {
    24     int ans = n;
    25     pre_kmp();
    26     for (int i = n; i > 0; i--)
    27     {
    28         int k = nexts[i];
    29         while (k > 0)
    30         {
    31             ans = (ans + 1) % mod;
    32             k = nexts[k];
    33         }
    34     }
    35     printf("%d\n", ans);
    36 }
    37 
    38 int main()
    39 {
    40     int T;
    41     scanf("%d", &T);
    42     while (T--)
    43     {
    44         scanf("%d", &n);
    45         scanf("%s", s);
    46         slove();
    47     }
    48     return 0;
    49 }

*  题目四：[Cyclic Nacklace][]

思路：题目大意：问至少添加多少个字符，使得这个字符串有至少两个循环节。若本身有两个循环节返回0，否则补充至两个循环节。

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<cstring>
     3 #include<iostream>
     4 using namespace std;
     5 
     6 const int mod = 10007;
     7 const int maxn = 200000 + 10;
     8 int nexts[maxn], n;
     9 char s[maxn];
    10 
    11 void pre_kmp()
    12 {
    13     int i = 0, j = nexts[0] = -1;
    14     n = strlen(s);
    15     while (i < n)
    16     {
    17         while (j != -1 && s[i] != s[j])  j = nexts[j];    //当前不匹配，j回退，寻找是否存在一个长度较小的字串和开头的字串相等
    18         nexts[++i] = ++j;                //j等于已匹配的长度，如果当前位置也匹配，则nexts直接为j+1
    19     }
    20 }
    21 
    22 void slove()
    23 {
    24     pre_kmp();
    25     int len = n - nexts[n];
    26     if (n % len  == 0 && nexts[n] != 0)  printf("0\n");
    27     else  printf("%d\n", len - nexts[n] % len);
    28 }
    29 
    30 int main()
    31 {
    32     int T;
    33     scanf("%d", &T);
    34     while (T--)
    35     {
    36         scanf("%s", s);
    37         slove();
    38     }
    39     return 0;
    40 }

参考链接：

1、[https://vjudge.net/contest/278481\#overview][https_vjudge.net_contest_278481_overview]

2、[https://blog.csdn.net/hkh746392783/article/details/52015293][https_blog.csdn.net_hkh746392783_article_details_52015293]

转载于:https://www.cnblogs.com/lfri/p/10341479.html

[1365470-20190131122459513-150838350.png]: /images/20230810/2afc11fcd78b421c9ab2068c4c74edaa.png
[1365470-20190131124532356-226085080.png]: /images/20230810/bb7b6bc1757841c6996b9a19f0488a3a.png
[1365470-20190131125339990-1474978713.png]: /images/20230810/2c66369efc444c158bbd9dce5f23d1b1.png
[Period]: https://vjudge.net/contest/278481#problem/C
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230810/7707152978f64813b8e751739bb8c951.png
[Power Strings]: https://vjudge.net/contest/278481#problem/D
[Count The String]: https://vjudge.net/contest/278481#problem/E
[Cyclic Nacklace]: https://vjudge.net/contest/278481#problem/F
[https_vjudge.net_contest_278481_overview]: https://vjudge.net/contest/278481#overview
[https_blog.csdn.net_hkh746392783_article_details_52015293]: https://blog.csdn.net/hkh746392783/article/details/52015293