Part2.2字符串算法-KMP 算法

A 剪花布条

KMP模板

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 10010;int n, m;
char s[N], p[N];
int ne[N];void work()
{
    for (int i = 2, j = 0; i <= m; i ++ ){
    while (j && p[i] != p[j + 1]) j = ne[j];if (p[i] == p[j + 1]) j ++;ne[i] = j;}int res = 0;int last = 0;for (int i = 1, j = 0; i <= n; i ++ ){
    while(j && s[i] != p[j + 1]) j = ne[j];if (s[i] == p[j + 1]) j ++;// cout << j << endl;if (j == m){
    // printf("i=%d,s[i]=%c,j=%d,p[j]=%c\n", i, s[i], j, p[j]);if (i - m >= last) res ++, last = i;// res ++;// j = 0;}}cout << res << endl;
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);while (cin >> s + 1){
    n = strlen(s + 1);if (s[1] == '#' && n == 1) return 0;cin >> p + 1;m = strlen(p + 1);memset(ne, 0, sizeof ne);work();}return 0;
}

B Power Strings

最小循环节

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 1000010;int n;
char s[N];
int ne[N];void work()
{
    for (int i = 2, j = 0; i <= n; i ++ ){
    while (j && s[i] != s[j + 1]) j = ne[j];if (s[i] == s[j + 1]) j ++;ne[i] = j;}int L = n - ne[n];if (n % L) puts("1");else printf("%d\n", n / L);
}
int main()
{
    while (cin >> s + 1){
    if (s[1] == '.') return 0;n = strlen(s + 1);memset(ne, 0, sizeof ne);work();}return 0;
}

C Radio Transmission

最小循环节

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 1000010;int n;
char s[N];
int ne[N];void work()
{
    for (int i = 2, j = 0; i <= n; i ++ ){
    while (j && s[i] != s[j + 1]) j = ne[j];if (s[i] == s[j + 1]) j ++;ne[i] = j;}int L = n - ne[n];cout << L << endl;
}
int main()
{
    cin >> n;cin >> s + 1;work();return 0;
}

OKR-Periods of Words

仔细看题目，Q为A的周期，条件如下，Q为A的前缀，且不等于A，同时A为QQ的前缀。
这就是说，Q为A的前缀，也为A的后缀（做题的关键）。
那么，最长周期的长度就好求了，就是i - 最短前后缀的长度，也就是j = ne[j]一直跳到ne[j]=0的位置

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 1000010;int n;
char s[N];
int ne[N];int main()
{
    cin >> n >> s + 1;for (int i = 2, j = 0; i <= n; i ++ ){
    while (j && s[i] != s[j + 1]) j = ne[j];if (s[i] == s[j + 1]) j ++;ne[i] = j;}long long res = 0;for (int i = 2, j; i <= n; i ++ ){
    j = i;//找到ne[j] = 0的j值，也就找到了最短公共前后缀的长度，，长度为jwhile (ne[j]) j = ne[j];//给ne更新到最短公共前后缀长度j，降低时间复杂度if (ne[i]) ne[i] = j;res += i - j;}cout << res << endl;return 0;
}