oppsbabanana_NTT
Rating
-
Bài tập
229
Điểm
24217
Rating #
-
Điểm #
1354
Giới thiệu
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int base1 = 311;
const int base2 = 331;
const int mod1 = 1e9 + 7;
const int mod2 = 1e9 + 9;
int mul(int a, int b)
{
if(b == 0)
return 1;
if(b == 1)
return a;
int x = mul(a, b / 2);
x = x * x;
if(b % 2 == 0)
return x;
return x * a;
}
main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int Test; Test = 1;
while(Test--)
{
int n; cin >> n;
string _ = "";
while(n--)
{
string s; cin >> s;
int kt = -1;
int h1 = 0, h2 = 0, h3 = 0, h4 = 0;
//cout << s << '\n';
for(int i = 0 ; i < min(s.size(), _.size()) ; i++)
{
h1 = h1 * base1 + (s[i] - 'a' + 1);
h2 = h2 + (_[_.size() - i - 1] - 'a' + 1) * mul(base1, i);
//cout << i << ' ' << h1 << ' ' << h2 << '\n';
if(h1 == h2)
{
kt = i;
}
}
//cout << kt << ' ' << _ << '\n';
for(int i = kt + 1 ; i < s.size() ; i++)
_.push_back(s[i]);
}
cout << _;
}
}