Compress Words

直接套 KMP 即可（那为什么打 cf 的时候没有想到...），求出后一个单词（word）的前缀数组，然后从前面已得的字符串的末尾 - word. length () 开始查询利用前缀数组进行优化即可

代码:

// Created by CAD on 2019/8/12.

#include <bits/stdc++.h>

using namespace std;

using pii=pair<int, int>;

using piii=pair<pair<int, int>, int>;

using ll=long long;

const int maxn=1e6+5;

int nxt[maxn];

void get_next(string s)

{

    int i=0,j=-1;nxt[0]=-1;

    int n=s.length();

    while(i<n)

    {

        if(j==-1||s[i]==s[j])

            nxt[++i]=++j;

        else j=nxt[j];

    }

}

string ans,word;

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    int n;cin>>n;

    for(int i=1;i<=n;++i)

    {

        cin>>word;

        int wlen=word.length();

        int alen=ans.length();

        get_next(word);

        int match=0;

        for(int j=max(alen-wlen,0);j<alen;++j)

        {

            while(match>0&&ans[j]!=word[match]) match=nxt[match];

            if(ans[j]==word[match]) match++;

        }

        ans+=word.substr(match);

    }

    cout<<ans<<endl;

    return 0;

}

巴特西

Compress Words

最新文章

热门文章