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

拿来复习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;
}

Div. 2 E. Compress Words（KMP）

全站热榜

创作者周榜