# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
107158701 |
Practice:
LTb |
1200E
- 114
|
C++17 (GCC 7-32)
|
Accepted
|
93 ms
|
15156 KB
|
2021-02-12 05:58:59 |
2021-02-12 05:59:00 |
|
// 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;
}
Click to see test details