[USACO15FEB]Censoring (Silver)

WA了一万次。。。。

然后发现多输出了一个空格

我#$%^&

启示我们输出字符的时候应该输出ASCII码看一下。。。。

然后本题可以用烤馍片算法，每次匹配完以后看看当前最后一位的nxt数组的值是多少，然后补齐到 lenT 。

下次匹配的时候直接从上次匹配过的最后一个开始匹配就行了。

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

char s[],t[],u[];

int nxt[],top,lent,lens,last;

void kmp() {

    for(int i=last+,j=nxt[last];i<=top;i++) {

        while(j&&u[i]!=u[j+]) j=nxt[j];

        if(u[i]==u[j+]) j++;

        nxt[i]=j;

    }

}

int main() {

    scanf("%s%s",s,t);

    lens=strlen(s),lent=strlen(t);

    for(int i=;i<lent;i++)

        u[i+]=t[i],u[i+lent+]=s[i];

    top=lent+lent+;

    u[lent+]=' ';

    int tp=lent-;

    for(int i=,j=;i<=lent+lent+;i++) {

        while(j&&u[i]!=u[j+]) j=nxt[j];

        if(u[i]==u[j+]) j++;

        nxt[i]=j;

    }

    last=;

    while(tp<lens) {

        kmp();

        if(nxt[top]==lent) top-=lent;

        last=top;

        for(int i=;i<=lent-nxt[last]&&tp<lens;i++)

        u[++top]=s[++tp];

    }

    for(int i=lent+;i<top;i++) printf("%c",u[i]);

}

Censoring