SCU 4438 Censor KMP/Hash

时间：2022-02-22 23:43:43

题意：给定一个模式串和文本，要求删除所有模式串。可能删除后会形成新的模式串，必须全部删除。

思路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;
}

如有不当之处欢迎指出！

相关文章