codeforces 1200E

$cf$上的题就是不板，综合考察对$kmp$的运用
题目链接

题目大意

给定$n$个字符串，从左到右依次把两个字符串合成一个，每两个合并的字符串，需要你找到最大的$i$，满足前字符串长度为$i$的后缀等于后字符串长度为$i$的前缀，把后字符串第$i$位以后的字符接到前字符串上，若没有相同的前后缀则直接拼接，输出最终结果

思路

题目要求找到相同的前缀和后缀，立刻想到要用$kmp$，但是$kmp$是在一个字符串内用的，所以每到两个字符串要链接时，我们先构造一个合起来的字符串$s$，对合起来的字符串进行$get$_$pmt$，找到失配数组$pmt$，要找的相同的前后缀数量就是$pmt[s.size()-1]$，注意一点：为了防止越过过度匹配超过自身长度，我们要在两个要链接的字符串中加一段乱码，如匹配$101$和$010$

ACcode

#include<bits/stdc++.h>

using namespace std;

const int M = 1e6 + 9;
int pmt[M];

void get_pmt(const string& p) {
    pmt[0] = 0;pmt[1] = 0;
    for (int i = 1, j = 0;i < p.size();i++) {
        while (j && p[i] != p[j])j = pmt[j - 1];
        if (p[i] == p[j])j++;
        pmt[i] = j;
    }
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;cin >> n;
    string ans;cin >> ans;
    string s;
    //cout << n << ' ' << ans;
    for (int i = 2;i <= n;i++) {
        cin >> s;
        int len = min(s.size(), ans.size());
        string ss = s + "(@#$%^&*!~~?><" + ans.substr(ans.size() - len, len);
        get_pmt(ss);
        //cout << ss << '\n';
        for (int j = pmt[ss.size() - 1];j < s.size();j++) ans += s[j];
    }
    cout << ans << '\n';
    return 0;
}