[USACO 2015] 删减 题解

题意：在字符串S中找到字符串T并将其删除，删除之后如果又合并出一个新的字符串T，则还要将其删除。

一开始感觉是用KMP，但发现KMP貌似不能连续删除，那该怎么办呢？（其实当时我不会KMP，hahaha）

又看了看题，感觉这个东西跟消消乐有点差不多，便让我想起了一个数据结构——栈。

每读取一个字符，就把它压到栈里，一旦栈顶的字符串等于T，就把它们全部弹掉，用Hash比较一下就行了。

模拟一下样例：

栈 当前字符

whatthemomo o

此时把o压到栈里

whatthemomoo o

发现栈顶3个元素的hash值等于T的hash值，弹栈

whatthemo o

再把下一个字符压到栈里

whatthemoo o

又发现栈顶3个元素的hash值等于T的hash值，再弹栈

whatthe o

这样一直扫下去就好了

这道题还是很简单的，主要是很有意思，有一种玩消消乐的感觉。

AC代码

#include<stdio.h>
#include<string.h>
unsigned long long hs[1000010],ht;
unsigned long long seed[110];
int n,m;
int top;
char S[1000010],stack[1000010],T[110];
void BKDR()
{
    seed[1]=131;
    ht=T[0];
    int i;
    for(i=1;i<m;i++)
    {
        ht=ht*seed[1]+T[i];
        seed[i+1]=seed[i]*seed[1];
    }
}
int main()
{
    scanf("%s%s",S,T);
    n=strlen(S);
    m=strlen(T);
    BKDR();
    int i,j;
    for(i=0;i<m;i++)
    {
        stack[top++]=S[i];
        hs[top]=hs[top-1]*seed[1]+S[i];
    }
    for(i=m;i<n;i++)
    {
        while(hs[top]-hs[top-m]*seed[m]==ht)
            for(j=0;j<m;j++)
                stack[--top]='\0';
        stack[top++]=S[i];
        hs[top]=hs[top-1]*seed[1]+S[i];
    }
    printf("%s",stack);
    return 0;
}

欢迎加入团队