CF1200E Compress Words

洛谷题目传送门

分析

模拟过程是先是前两个单词合并，合并之后的句子再接着和第三个单词合并这样子

所以过程中肯定是要开个 \(ans\) 串不断去进行合并预处理和答案累加

合并单词 \(a\) 和单词 \(b\) 时，要得到最大的长度 \(len\) ，消除 \(a\) 的后缀 \(len\) 或者消除 \(b\) 的前缀，

但是 \(a\) 是答案串，直接消除 \(b\) 的前缀更好。

接下来要确定 \(len\) 的求法，如果我们把 \(b\) 串放在 \(a\) 串前面，那么要消除的这个最大长度，

不正好就是就是 \(next[总长度]\) 吗
再仔细考虑，匹配的最大长度肯定不会超过 \(b\) 串的长度，为了避免 \(a\) 串过长，我们可以删掉它前面大于 \(b\) 串长度的部分

所以思路确定下来：
 1.先把 \(b\) 串放在处理后的 \(ans\) 串前面，中间用特殊字符分开；
 2.对合成后的串求next数组，得到 \(d\) 为最大匹配长度（即 \(b\)要消除的长度)
 3.把 \(b\) 前面消除后加到 \(ans\) 串里

代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define rg register
inline int read(){
    rg int x = 0, f = 1;
    rg char c = getchar();
    while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return x * f;
}
const int N = 1e6 + 1;
int n;
int net[N];
int prenext(string a){
    net[0] = 0;
    int len = a.length();
    for (int i = 1; i < len; ++i){
        int j = net[i - 1];
        while (j && a[j] != a[i]) j = net[j - 1];
        if (a[j] == a[i]) net[i] = j + 1;
        else net[i] = 0;
    }
    return net[len - 1];
}

inline void doit(){
    cin >> n;
    string b, ans;
    cin >> ans;
    for (int i(2); i <= n; ++i){
        cin >> b;
        int l = min(b.size(), ans.size());
        string a = b + "#" + ans.substr(ans.size() - l, l);
        b.erase(0, prenext(a));
        ans += b;
    }
    cout << ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    //freopen("in.txt", "r", stdin);
    doit();
    return 0;
}