HDU1711 Number Sequence
题目链接
题意：给定数组 $a_i(1\le i\le n)$ 和 $b_i(1\le i\le m)$，求最小的 $k$ 满足 $a_k=b_1,\cdots,a_{k+m-1}=b_m$。
KMP 模板题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f, N = 1e6 + 5, M = 1e4 + 5;
int t, n, m;
int a[N], b[M];
int nxt[M];
void getnext() {
nxt[0] = -1;
int j = -1;
for (int i = 1; i < m; ++i) {
while (j != -1 && b[i] != b[j+1]) j = nxt[j];
if (b[i] == b[j+1]) j++;
nxt[i] = j;
}
}
int kmp() {
int j = -1;
for (int i = 0; i < n; ++i) {
while (j != -1 && a[i] != b[j+1]) j = nxt[j];
if (a[i] == b[j+1]) j++;
if (j == m - 1) return i - m + 2;
}
return -1;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> t;
while (t--) {
cin >> n >> m;
for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i < m; ++i) cin >> b[i];
getnext();
cout << kmp() << '\n';
// for (int i = 0; i < m; ++i) cout << nxt[i] << " \n"[i == m - 1];
}
return 0;
}
|
HDU1686 Oulipo
题目链接
题意：给出单词 $W(1\le|W|\le1e4)$ 和文本 $T(|W|\le|T|\le1e6)$，求 $W$ 在 $T$ 中出现次数。
KMP 模板题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f, M = 1e4 + 5;
int t, n, m;
string W, T;
int nxt[M];
void getnext() {
nxt[0] = -1;
int j = -1;
for (int i = 1; i < m; ++i) {
while (j != -1 && W[i] != W[j+1]) j = nxt[j];
if (W[i] == W[j+1]) j++;
nxt[i] = j;
}
}
int kmp() {
int res = 0, j = -1;
for (int i = 0; i < n; ++i) {
while (j != -1 && T[i] != W[j+1]) j = nxt[j];
if (T[i] == W[j+1]) j++;
if (j == m - 1) res++, j = nxt[j];
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> t;
while (t--) {
cin >> W >> T;
n = T.length(), m = W.length();
getnext();
cout << kmp() << '\n';
}
return 0;
}
|
HDU2087 剪花布条
题目链接
题意：求子串不重叠出现次数。
和上题一样，改一点就行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f, M = 1e3 + 5;
int n, m;
string a, b;
int nxt[M];
void getnext() {
nxt[0] = -1;
int j = -1;
for (int i = 1; i < m; ++i) {
while (j != -1 && b[i] != b[j+1]) j = nxt[j];
if (b[i] == b[j+1]) j++;
nxt[i] = j;
}
}
int kmp() {
int res = 0, j = -1;
for (int i = 0; i < n; ++i) {
while (j != -1 && a[i] != b[j+1]) j = nxt[j];
if (a[i] == b[j+1]) j++;
if (j == m - 1) res++, j = -1;
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
while (cin >> a && a[0] != '#') {
cin >> b;
n = a.length(), m = b.length();
getnext();
cout << kmp() << '\n';
}
return 0;
}
|
POJ2752 Seek the Name, Seek the Fame
题目链接
题意：求字符串既是前缀又是后缀的子串长度。
拓展 KMP。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f, N = 4e5 + 5;
int n;
string s;
int z[N];
void getz() {
memset(z, 0, sizeof(z));
int l = 0, r = 0;
for (int i = 1; i < n; ++i) {
if (i <= r) z[i] = min(r - i + 1, z[i-l]);
while (i + z[i] < n && s[i+z[i]] == s[z[i]]) z[i]++;
if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
while (cin >> s) {
n = s.length();
getz();
for (int i = n - 1; i > 0; --i) {
if (i + z[i] == n) cout << z[i] << ' ';
}
cout << n << '\n';
}
return 0;
}
|
HDU3068 最长回文
题目链接
题意：多组输入，求字符串所包含的最长回文长度。
manacher 裸模板题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
typedef pair<int, int> pii;
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 3e5 + 5;
int n, p[N], ans;
char s[N], str[N];
void init() {
str[0] = str[1] = '#';
for (int i = 0; i < n; ++i) {
str[(i<<1)+2] = s[i];
str[(i<<1)+3] = '#';
}
n = (n<<1) + 2; str[n] = 0;
}
void manacher() {
int maxr = 0, id = 0;
for (int i = 1; i < n; ++i) {
if (maxr > i) p[i] = min(p[2*id-i], maxr - i);
else p[i] = 1;
while (str[i+p[i]] == str[i-p[i]]) ++p[i];
if (i + p[i] > maxr) { maxr = i + p[i]; id = i; }
ans = max(ans, p[i] - 1);
}
}
int main()
{
while (~scanf("%s", s)) {
n = strlen(s);
ans = 0;
init();
manacher();
printf("%d\n", ans);
}
return 0;
}
|