Pagini recente » Cod sursa (job #445119) | Cod sursa (job #968468) | Cod sursa (job #3187255) | Cod sursa (job #2552907) | Cod sursa (job #1006341)
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
const unsigned int maxl = 30000,
maxn = 18;
unsigned int N;
string s[maxn];
unsigned short kmpTable[maxn][maxl],
used[maxn];
ifstream fileInStream("adn.in");
ofstream fileOutStream("adn.out");
void createKmpTable(string a, unsigned short *table) {
unsigned int x = 0, it = 0;
table[0] = 0;
for(int i = 1; i < a.length(); ++i) {
if(a[i] == a[it]) {
++x;
table[i] = x;
++it;
} else {
it = 0;
x = 0;
if(a[i] == a[it]) {
++x;
table[i] = x;
++it;
} else {
table[i] = x;
++it;
}
}
}
}
int kmpSearch(string pattern, string in, unsigned short *kmpTable) {
unsigned int index = 0, match = 0;
while(index + match < in.length()) {
if(pattern[match] == in[index + match]) {
++match;
if(match >= pattern.length()) {
return index;
}
} else {
if(match > 0) --match;
index = index + 1 + match - kmpTable[match];
match = 0;
}
}
return -1;
}
inline void read() {
fileInStream >> N;
for(int i = 0; i < N; i++) {
fileInStream >> s[i];
used[i] = 0;
createKmpTable(s[i], kmpTable[i]);
}
}
inline void write() {
for(int i = 0; i < N; ++i) {
if(used[i] == 0) {
fileOutStream << s[i];
}
}
}
bool equals(string s1, unsigned int pos1, string s2, unsigned int pos2, unsigned int length) {
unsigned int i = pos1, j = pos2;
while(i - pos1 < length) {
if(s1[i] != s2[j]) {
return false;
}
++i; ++j;
}
return true;
}
bool finished() {
int n = 0;
for(int i = 0; i < N; ++i) {
if(used[i] != 1) {
++n;
}
}
if(n > 1) {
return false;
}
return true;
}
inline void solve() {
int j, k, x,
index = -1, l;
while(!finished()) {
for(int i = 0; i < N; ++i) {if(used[i] == 1) continue;
for(j = 0; j < N; ++j) {
if(i != j && used[j] != 1) {
if(s[i].length() >= s[j].length() && kmpSearch(s[j], s[i], kmpTable[j]) != -1) {
used[j] = 1;
}
}
}
for(j = 0; j < N; ++j) {if(i == j || used[j]) continue;
s[i] > s[j] ? k = s[j].length() : k = s[i].length()-1;
for(; k > 0; --k) {
if(equals(s[i], s[i].length()-k, s[j], 0, k)) {
if(index == -1 || k > l) {
l = k;
index = j;
}
}
}
}
if(index != -1) {
s[i] += s[index].substr(l, s[index].length() - l);
used[index] = 1;
index = -1;
}
}
}
}
int main() {
int i;
read();
solve();
write();
return 0;
}