Div. 2 E. Compress Words(KMP)

题意:给一串单词依次连接(第一个和第二个,加起来再和第三个......),连接时前一个单词和后一个单词最长的前后缀重合,问最后的句子

拿来复习KMP。。实在太久没写过KMP了,
KMP通过求解最长相同前后缀进行字符串匹配,next数组为最长长度表右移一位得到。
KMP过程中求得是:模式串的前缀与母串的后缀最长相同长度
i代表当前母串匹配位置,每轮匹配 j 初始值为i-1位置母串对应的最长相同前后缀末端位置+1,
如果此时满足,母串[ i ]=模式串[ j+1 ],则当前最长相同前后缀末端为nxt[ i-1 ]+1 (++j)
因为nxt数组其实是长度表右移,所以最后求 next数组代码为:
//对tmp求nxt
        int len=tmp.length();
        int j=0;
        nxt[0]=nxt[1]=0;
        for(int i=2;i<=len;++i)
        {
            while(j&&tmp[i-1]!=tmp[j]) j=nxt[j];
            if(tmp[i-1]==tmp[j]) ++j;
            nxt[i]=j;
        }
题中要求tmp与答案串中,tmp的前缀与答案串的后缀的最长相同长度,套板子
#include<bits/stdc++.h>
using namespace std;
#define endll '\n'
#define C getchar()
typedef long long ll;
#define pi acos(-1.0)
#define INF 0x3f3f3f3f
#define mod 998244353
#define pii pair<int, int>
const int MAXN = 1e6 + 10;
#define stop system("pause")
#define lowbit(x) ((x) & (-x))
#define Temp template<typename T>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define mem(a, b) memset(a, b, sizeof(a))
#define fast std::ios::sync_with_stdio(false)
Temp inline void rd(T &s)
{
    s = 0;T t = 1, k = C;
    for (; k < '0' || k > '9'; k = C)if (k == '-') t = -1;
    for (; k >= '0' && k <= '9'; k = C) s = (s << 1) + (s << 3) + (k ^ 48);
    s *= t;
}


string a;
int nxt[MAXN];
int main()
{
    int n;rd(n);
    cin>>a;
    for(int _=1;_<n;++_)
    {
        string tmp;
        cin>>tmp;
        //对tmp求nxt
        int len=tmp.length();
        int j=0;
        nxt[0]=nxt[1]=0;
        for(int i=2;i<=len;++i)
        {
            while(j&&tmp[i-1]!=tmp[j]) j=nxt[j];
            if(tmp[i-1]==tmp[j]) ++j;
            nxt[i]=j;
        }
        j=0;
        int anslen=a.length();
        for(int i=max(1,anslen-len+1);i<=anslen;++i)
        {
            while(j&&a[i-1]!=tmp[j]) j=nxt[j];
            if(a[i-1]==tmp[j]) ++j;
        }
        for(int i=j;i<len;++i) a+=tmp[i];
    }
    cout<<a<<endll;
    //stop;
    return 0;
}



全部评论

相关推荐

不愿透露姓名的神秘牛友
07-16 14:00
白火同学:其实你可以了解一下HR在Boss聊天的机制,想赢牌的前提是先会玩牌。 如果HR长时间没有理你,有可能是因为你的消息被其他应聘者的消息给挤到下面了,HR从上到下有可能只看个三四百个人就要到理想数量的简历了,而你恰好没有被看到,时间一长,你的消息在越来越下面。这种情况就需要你自己活跃一下,把消息提上去。 也可能是HR招的合适的人选了,但会一直挂着岗位,为了省重新开招聘岗位的钱,方便后面随时修改招聘要求。 当然也可能是HR吃饱了没事耍你玩,要了你的简历又不看,就看你自己怎么理解了。
点赞 评论 收藏
分享
07-18 14:55
门头沟学院 Java
点赞 评论 收藏
分享
码砖:求职岗位要突出,一眼就能看到,教育背景放到最后,学校经历没那么重要,项目要重点突出
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务