本文共 1104 字，大约阅读时间需要 3 分钟。

题意是将多个单词连接起来，使得前后两个单词去掉公共后缀和前缀后形成一个完整的新单词。简单来说，就是通过去除重复的部分，拼接成一个新单词。

解决这个问题的思路源于KMP算法中的后缀匹配方法。我们可以倒序匹配，将前缀和后缀的重叠部分去掉，剩下的部分再拼接起来作为最终结果。为了防止哈希冲突，我们引入了双模数哈希：一个用于防止取模运算溢出，另外一个用于防止哈希冲突。

以下是实现代码：

#include 
   
    
using namespace std;
#define debug printf("---\n");
const int N=210, M=10010;
#define debug(a) cout << a << endl;
const unsigned long bas="131;
const int mod1="1e9+9;
const int mod2="999999998;
int main() {
    ios::sync_with_stdio();
    cin.tie(0);
    string ans, s;
    cin >> ans;
    for(int i=2; i<=n; i++) {
        string s;
        // ... 读取输入 ...
        // 双模数哈希
        for(int j=1; j<=min(s.size(), ans.size()); j++) {
            ll p1 = (p1 + ans[ans.size()-j] * tmp) % mod1;
            ll p2 = (s[j-1] + p2 * bas) % mod1;
            ll p11 = (p11 + ans[ans.size() -j] * tmp2) % mod2;
            ll p22 = (s[j-1] + p22 * bas) % mod2;
            if(p1==p2 && p22==p11)
                maxv = j;
        }
        ans += s.substr(maxv);
    }
    // ... 输出结果 ...
}
   

另一种方法是使用KMP算法的预处理和匹配阶段。具体步骤如下：

这个方法简单高效，适合处理大量单词连接问题。