General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
107158701 Practice:
LTb
1200E - 114 GNU C++17 Accepted 93 ms 15156 KB 2021-02-12 05:58:59 2021-02-12 05:59:00
 
 
→ Source
// 2021.02.12 - 10:32
// Code by LTb
// #pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define debug puts("QwQ");
inline int read(){
    int x=0,f=1;
    char ch;
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    return f*x;
}

inline char readch(){
	char ch=getchar();
	while (ch==' '||ch=='\n') ch=getchar();
	return ch;
}

inline string readstr(){
	char ch=getchar();
	string ans="";
	while (ch==' '||ch=='\n') ch=getchar();
	while (ch!=' '&&ch!='\n') {ans+=ch;ch=getchar();}
	return ans;
}

inline void chmax(int &x,int y){x=max(x,y);}
inline void chmin(int &x,int y){x=min(x,y);}
// inline void pls(int &x,int y,int Mod){x=(x+y>=Mod)?(x+y-Mod):(x+y);}
// inline void red(int &x,int y,int Mod){x=(x-y<0)?(x-y+Mod):(x-y);}

const int MAXN = 100005;
const int MAXM = 2000005;
int n;
string s[MAXN];
int nex[MAXM];

string ans, y;

inline char pos(int x, int mx) {
	if (x <= mx) return y[x - 1];
	else if (x == mx + 1) return '#';
	else return ans[ans.size() - mx + (x - mx - 1) - 1];
}

// x 是前面拼接好的,y 是待拼接的
int merge() {
	int mx = min(int(ans.size()), int(y.size()));

	// for (int i = 1; i <= mx * 2 + 1; i++)
	// 	cout<<pos(i, mx);
	// cout<<endl;

	// string a = y + '#' + x;
	for (int i = 2, j = 0; i <= mx * 2 + 1; i++) {
		while (j > 0 && pos(i, mx) != pos(j + 1, mx)) j = nex[j];
		if (pos(i, mx) == pos(j + 1, mx)) j++;
		nex[i] = j;
	}

	return nex[mx * 2 + 1];
}

signed main()

{
	n = read();
	for (int i = 1; i <= n; i++)
		s[i] = readstr();

	ans = s[1];
	for (int i = 2; i <= n; i++) {
		y = s[i];
		int num = merge();
		// cout << ans << ' ' << s[i] << ' ' << num << endl;
		ans += s[i].substr(num);
	}

	cout << ans << endl;
	return 0;
}
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details