[数据结构与算法]总结20220208

上午看了kmp算法的思想，不是很懂，下午又查了一些kmp的模板，还不是很清楚具体的步骤，但是在模板的基础上做了一个题。明天再仔细看看细节。

Compress Words

题目描述

Amugae has a sentence consisting of?nn?words. He want to compress this sentence into one word. Amugae doesn't like repetitions, so when he merges two words into one word, he removes the longest prefix of the second word that coincides with a suffix of the first word. For example, he merges "sample" and "please" into "samplease".

Amugae will merge his sentence left to right (i.e. first merge the first two words, then merge the result with the third word and so on). Write a program that prints the compressed word after the merging process ends.

输入格式

The first line contains an integer?nn?(?1 \le n \le 10^51≤n≤105?), the number of the words in Amugae's sentence.

The second line contains?nn?words separated by single space. Each words is non-empty and consists of uppercase and lowercase English letters and digits ('A', 'B', ..., 'Z', 'a', 'b', ..., 'z', '0', '1', ..., '9'). The total length of the words does not exceed?10^6106?.

输出格式

In the only line output the compressed word after the merging process ends as described in the problem.

题意翻译

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

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int t[N];
char s[N],p[N];
int len1,len2;
void next(char p[])    //求前缀表数组t 
{
    int j,i;
    j=-1;
    t[0]=-1;
    i=0;
    while(i<len2-1)
    {
        if(j==-1||p[i]==p[j])
        {
            i++;
            j++;
            if(p[i]!=p[j]) t[i]=j;
            else t[i]=t[j];
        }
        else
            j=t[j];
    }
}
int kmp(char s[],char p[])
{
    int i,j;
    i=max(0,len1-len2);
    j=0;
    next(p);
    while(i<len1)
    {
        while(s[i]!=p[j])//当不匹配时，开始考虑next数组
        {
            if(t[j]==0)//如果子串中没有前后缀，子串从头开始匹配
            {
                j=0;
                break;
            }
            else//子串有最大相同前后缀，j从next[j]处重新开始匹配
                j=t[j];
        }
        if(s[i]==p[j]) j++;
        i++;
    }
    return j;          //走遍母串去找子串的位置
}
int main()
{
    int n,i,j;
    cin>>n;
    cin>>s;
    n-=1;
    len1=strlen(s);
    while(n--)
    {
        cin>>p;
        len2=strlen(p);
        int c=kmp(s,p);
        i=len1-c;
        for(j=0;j<len2;j++)
        {
            s[i++]=p[j];      //将新字符串加在长字符串后面 
        }
        s[i]='\0';
        len1+=len2-c;
    }
    cout<<s;
    return 0;
}