KMP
#include<bits/stdc++.h> using namespace std; int p[1000005]; int len; void getNext(char *s) { int i=0,j=-1; p[0]=-1; int n=strlen(s); for(i; i<n;) { if(j==-1||s[i]==s[j]) { i++; j++; if(s[i]==s[j]) p[i]=p[j]; else p[i]=j; } else { j=p[j]; } } //return j; } int KMP(char *s,char *t) { int n=strlen(t); int i=max(0,len-n),j=0; getNext(t); for(i; i<len;) { while(s[i]!=t[j]) { if(p[j]==0) { j=0; break; } else j=p[j]; } if(s[i]==t[j]) { j++; } i++; } return j; } char s[1000004]; char t[1000004]; int main() { int T; scanf("%d",&T); scanf("%s",s); len=strlen(s); T--; for(int _=0;_<T;_++){ scanf("%s",t); int c=KMP(s,t); //int n=strlen(s); int m=strlen(t); int i=len-c; for(int j=0;j<m;j++){ s[i++]=t[j]; }s[i]=' '; len+=m-c; } cout<<s<<' '; }