题意:给定一个模式串和文本,要求删除所有模式串。可能删除后会形成新的模式串,必须全部删除。
思路1:kmp算法求得失配数组,用一个match数组记录文本串中第i字符和未删除的字符能匹配模式串的长度。这样每次删除字符串之后就不用再匹配,直接查询match数组即可。用栈模拟,自己实现的栈可以加快速度。
AC代码
#include <cstdio>
#include <cmath>
#include <cctype>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <utility>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define eps 1e-10
#define inf 0x3f3f3f3f
#define PI pair<int, int>
typedef long long LL;
const int maxn = 5e6 + 5;
int fail[maxn]; //失配数组
int match[maxn];
char p[maxn], w[maxn], ans[maxn];
void getFail(char *s, int *fail, int n) {
fail[0] = -1;
for(int i = 1; i < n; ++i) {
int j = fail[i-1];
while(j != -1 && s[j+1] != s[i]) j = fail[j];
if(s[j+1] == s[i]) fail[i] = j+1;
else fail[i] = -1;
}
}
int top;
int sta[maxn];
void kmp(char *p, char *w, int *fail) {
int n = strlen(w), m = strlen(p);
getFail(w, fail, n);
top = 0;
int now = -1;
for(int i = 0; i < m; ++i) {
ans[top] = p[i];
while(now != -1 && w[now+1] != p[i]) now = fail[now];
if(w[now+1] == p[i]) {
now = now + 1;
}
match[i] = now;
sta[++top] = i;
//成功匹配w
if(now == n-1) {
top -= n;
if(top == 0) now = -1;
else now = match[sta[top]];
}
}
ans[top] = '\0';
}
int main() {
while(scanf("%s%s", w, p) == 2) {
kmp(p, w, fail);
printf("%s\n", ans);
}
return 0;
}
思路2:哈希技术真的好玄学。一直判断最后strlen(w)字符的哈是值是否和模式串的哈希一致,如果一致就删除。
#include <cstdio>
#include <cmath>
#include <cctype>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <utility>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define eps 1e-10
#define inf 0x3f3f3f3f
#define PI pair<int, int>
typedef long long LL;
const int maxn = 5e6 + 5;
const int seed = 100003;
LL bit[maxn];
char p[maxn], w[maxn], ans[maxn];
LL sta[maxn];
void getBit() {
bit[0] = 1;
for(int i = 1; i < maxn; ++i)
bit[i] = bit[i-1]*seed;
}
LL getHash(char *s, int len) {
LL res = 0;
for(int i = 0; i < len; ++i)
res = res*seed + s[i];
return res;
}
void solve(char *p, char *w) {
int n = strlen(w), m = strlen(p);
LL goal = getHash(w, n);
//栈 top=0表示栈空
int top = 0;
sta[top] = 0;
for(int i = 0; i < m; ++i) {
ans[top] = p[i];
LL res = sta[top] * seed + p[i];
sta[top++] = res;
if(top >= n && res - sta[top-n]*bit[n] == goal) {
top -= n;
}
}
ans[top] = '\0';
printf("%s\n", ans);
}
int main() {
getBit();
while(scanf("%s%s", w, p) == 2) {
solve(p, w);
}
return 0;
}
如有不当之处欢迎指出!