博客

下午把昨天剩下的一道题给补了

题意翻译

Amugae有n个单词,他想把这个n个单词变成一个句子,具体来说就是从左到右依次把两个单词合并成一个单词.合并两个单词的时候,要找到最大的i(i\ge 0)i(i≥0),满足第一个单词的长度为ii的后缀和第二个单词长度为ii的前缀相等,然后把第二个单词第ii位以后的部分接到第一个单词后面.输出最后那个单词

输入输出样例

输入 #1

复制

5
I want to order pizza

输出 #1

复制

Iwantorderpizza

输入 #2

复制

5
sample please ease in out

输出 #2

复制

sampleaseinout

两个单词两个单词的合并，刚好发现要去掉的就是它的最长公共前后缀（

ple

ase.sam

ple

），就是kmp里的那部分了，只需要最长公共前后缀后面的字符拼接上去，这个也只需要截取单词长度最小的那个长度，因为多余的部分也用不上，这个还要在这两者之间加一个不一样的字符就行了，来防止求最长前后缀的时候不会超出这个单词的长度，然后直接截取最长公共前后缀后面的字符

#include<bits/stdc++.h>
#include<string>
using namespace std;

int Next[1000000];

void get_next(string s2)
{
    int i = 0,j = -1;
    Next[0] = -1;
    while(i < s2.length()){
        if(j == -1 || s2[i] == s2[j]){
            i++;
            j++;
            Next[i] = j;
        }
        else{
            j = Next[j];
        }
    }
}

int main()
{
    int n;
    string s1;
    cin >> n;
    cin >> s1;
    for(int q = 1;q < n;q++){
        string s2,s3;
        cin >> s2;
        int len1 = s1.length(),len2 = s2.length();
        int len = min(len1,len2);
        s3 = s2.substr(0,len) + "." + s1.substr(len1 - len,len1);//只需要求s3最长公共前后缀
        get_next(s3);
        s1 += s2.substr(Next[s3.length()],len2);
       // cout << s1 <<endl;
    }
    cout << s1 << endl;
}

然后看了啊哈算法的最短路径