模板
caioj 1177 KMP模板
#include<bits/stdc++.h>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 1e6 + 10;
const int MAXM = 1e3 + 10;
char a[MAXN], b[MAXM];
int next[MAXM], lena, lenb; void get_next()
{next[1] = 0; int j = 0;_for(i, 2, lenb){while(j > 0 && b[j + 1] != b[i]) j = next[j];if(b[j + 1] == b[i]) j++;next[i] = j; }
}void kmp()
{int j = 0;_for(i, 1, lena){while(j > 0 && (j == lenb || b[j + 1] != a[i])) j = next[j]; if(b[j + 1] == a[i]) j++;if(j == lenb) { printf("%d %d\n", i - lenb + 1, i); return; } }puts("NO");
}int main()
{scanf("%s%s", a + 1, b + 1);lena = strlen(a + 1); lenb = strlen(b + 1);get_next();kmp();return 0;
}caioj 1460: 【KMP】字符串匹配
#include<bits/stdc++.h>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 1e6 + 10;
char a[MAXN], b[MAXN];
int next[MAXN], lena, lenb;void get_next()
{next[1] = 0; int j = 0;_for(i, 2, lena){while(j > 0 && a[j + 1] != a[i]) j = next[j];if(a[j + 1] == a[i]) j++;next[i] = j;}
}int kmp()
{int res = 0, j = 0;_for(i, 1, lenb){while(j > 0 && a[j + 1] != b[i]) j = next[j];if(a[j + 1] == b[i]) j++;if(j == lena) { res++; j = next[j]; } } return res;
} int main()
{int T;scanf("%d", &T);while(T--){scanf("%s%s", a + 1, b + 1);lena = strlen(a + 1); lenb = strlen(b + 1); get_next();printf("%d\n", kmp());}return 0;
}重复子串结论
有一个结论。
对于字符串S[1~i],如果i % (i - next[i]) == 0，那么这个字符串就由很多个重复的子串构成（形如abababab）
每个循环节等于S[1~i-next[i]]，循环节的个数为i / (i - next[i])
这个结论很好证明，用笔画一下就可以发现这个性质
caioj 1457: 【KMP】重复的子串
#include<bits/stdc++.h>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 1e6 + 10;
char a[MAXN];
int next[MAXN], lena; void get_next()
{next[1] = 0; int j = 0;_for(i, 2, lena){while(j > 0 && a[j + 1] != a[i]) j = next[j];if(a[j + 1] == a[i]) j++;next[i] = j; }
}int main()
{while(scanf("%s", a + 1)){if(a[1] == '.') break;lena = strlen(a + 1);get_next();if(lena % (lena - next[lena]) == 0) printf("%d\n", lena / (lena - next[lena]));else puts("1");}return 0;
}caioj 1458: 【KMP】判断循环段位置
#include<bits/stdc++.h>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 1e6 + 10;
char a[MAXN];
int next[MAXN], lena; void get_next()
{next[1] = 0; int j = 0;_for(i, 2, lena){while(j > 0 && a[j + 1] != a[i]) j = next[j];if(a[j + 1] == a[i]) j++;next[i] = j; }
}int main()
{scanf("%s", a + 1);lena = strlen(a + 1);get_next();_for(i, 2, lena)if(i % (i - next[i]) == 0 && i / (i - next[i]) > 1)printf("%d %d\n", i, i / (i - next[i]));return 0;
}next数组应用
caioj 1459: 【KMP】所有前缀等于后缀的情况
#include<bits/stdc++.h>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 1e6 + 10;
char a[MAXN];
int next[MAXN], lena; void get_next()
{next[1] = 0; int j = 0;_for(i, 2, lena){while(j > 0 && a[j + 1] != a[i]) j = next[j];if(a[j + 1] == a[i]) j++;next[i] = j; }
}int main()
{while(~scanf("%s", a + 1)){lena = strlen(a + 1);get_next();int j = lena;stack<int> s;while(j) s.push(j), j = next[j];while(!s.empty()) printf("%d ", s.top()), s.pop();puts("");}return 0;
}综合题
poj 2185
这道题不知道为什么一直A不了。先放着
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 1e4 + 10;
const int MAXM = 75 + 10;
char s[MAXN][MAXM], t[MAXN];
int next[MAXN], f[MAXN];
int n, m, r, c, j;int get_r() //一行看作一个字符，很牛逼。
{next[1] = 0;for(int i = 2, j = 0; i <= n; i++){if(j > 0 && strcmp(s[j + 1], s[i])) j = next[j];if(!strcmp(s[j + 1], s[i])) j++;next[i] = j;}return n - next[n];
}int get_c()
{memset(f, 0, sizeof(f));_for(i, 1, n)_for(len, 1, m)REP(j, 0, m){if(s[i][j] != s[i][j % len]) break; //这个操作要学学 if(j == m - 1) f[len]++;} _for(i, 1, m) //用桶这个思路很妙 if(f[i] == n)return i;
}int main()
{scanf("%d%d", &n, &m); _for(i, 1, n) scanf("%s", s[i]);printf("%d\n", get_r() * get_c());return 0;
}