ZOJ 3643 Keep Deleting(KMP + 栈)

题目大意

给定长度为 $N$ 的字符串 $A$ 和长度为 $M$ 的字符串 $B$。每次从左往右看,如果发现 $A$ 作为 $B$ 的 $substring$ 出现,那么在 $B$ 中删除 $A$。对新的字符串递归进行此操作。求最大删除次数。
$( N \leq 256, M \leq 512000)$

解题思路

KMP + 栈

首先对字符串 $A$ 进行 $KMP$ 的预处理操作,得到 $Next[i]$ 。

然后从左往右遍历字符串 $B$,按照 $KMP$ 算法进行匹配操作,并用一个栈维护 “$B$ 中已经扫描过但仍未被删除的字符与模式串 $A$ 中对应字符的匹配位置”,如此,每当 $KMP$ 成功匹配一次,答案加 $1$,把栈顶的 $A.length()$ 个元素出栈,并让模式串 $A$ 的匹配位置回退到现在栈顶元素所保存的位置。一直遍历到 $B$ 结束。

Note: 似乎不用KMP,单纯使用strcmp()函数 + 栈也可以过。

代码

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
48
49
50
51
52
53
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>

using namespace std;

typedef long long ll;

const int MAXN = 256 + 10;
const int MAXM = 512000 + 10;

char A[MAXN], B[MAXM];
int Next[MAXN], Stack[MAXM];

void getNext()
{

int i = 0, j = Next[0] = -1, len = strlen(A);
while( i < len )
{
while( ~j && A[i] != A[j] ) j = Next[j];
if( A[++i] == A[++j] ) Next[i] = Next[j];
else Next[i] = j;
}
}
int main()
{

while( ~scanf("%s %s", A, B) )
{
getNext();
int Alen = strlen(A), Blen = strlen(B);
int top = 0, j = 0, ans = 0;
for( int i = 0; i < Blen; ++ i )
{
while( ~j && B[i] != A[j] ) j = Next[j];
Stack[top++] = ++j;
if( j == Alen )
{
ans++;
top -= Alen;
j = Stack[top - 1];
}
}
printf("%d\n", ans);
}

return 0;
}

Ps: KMP老是忘…这可不太妙,每次都要重新理解太浪费时间了…还是要多 review。

如果您觉得这篇博文对您有所帮助,可以考虑请我吃颗糖哦!