6. Idiomatická rekonštrukcia vzorové riešenie

from string import ascii_lowercase

size = len(ascii_lowercase)


class Node:
    def __init__(self):
        self.children = {}

    def existing_children(self):
        return set(self.children.keys())


def add_word(word: str, root: Node):
    v = root
    for c in word:
        if c not in v.children:
            v.children[c] = Node()
        v = v.children[c]


n = int(input())
words = [input() for _ in range(n)]

prefix = Node()
suffix = Node()

for word in words:
    add_word(word, prefix)
    add_word(word[::-1], suffix)

q = [(prefix, suffix, "")]

while q:
    p, s, w = q.pop(0)

    p_child = p.existing_children()
    if len(p_child) == 0:
        p = prefix
        p_child = p.existing_children()

    s_child = s.existing_children()
    if len(s_child) == 0:
        s = suffix
        s_child = s.existing_children()
    
    if p == prefix and s == suffix and w != "":
        print(w+w[::-1])
        exit(0)

    child = p_child.intersection(s_child)
    for i in child:
        q.append((p.children[i], s.children[i], w+i))

print(-1)

#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct trie_node{
    trie_node* parent;
    trie_node* children[26];
    int depth;
    bool end;
    int id;
};

trie_node* new_node(trie_node* parent, int letter, int id){
    trie_node* o = new trie_node;
    if(parent != NULL){
        parent->children[letter] = o;
        o->depth = parent->depth + 1;
    }else{
        o->depth = 0;
    }
    o->id = id;
    o->parent = parent;
    o->end = false;
    for(int i = 0; i < 26; i++){
        o->children[i] = NULL;
    }
    return o;
}

int save_word(trie_node* where, string s, bool reverse, int offset, int ids){
    if(offset == s.length()){
        where->end = true;
        return ids-1;
    }
    int l;
    if(reverse){
        l = s[s.length()-1-offset]-'a';
    }else{
        l = s[offset]-'a';
    }
    if(where->children[l] == NULL){
        trie_node* o = new_node(where,l,ids);
        ids++;
        ids = save_word(o,s,reverse,offset+1,ids);
    }else{
        ids = save_word(where->children[l],s,reverse,offset+1,ids);
    }
    return ids;
}

trie_node* find_node(trie_node* where,string s,int offset){
    if(offset == s.length()){
        return where;
    }
    
    return find_node(where->children[s[offset]-'a'],s,offset+1);
    
}

char vyries(trie_node* pre,trie_node* post,vector<char>& result,bool** visited,char** goal,trie_node* posl,trie_node* posr,bool ignore = false){
    
    if(posl->end){
        posl = pre;
    }
    if(posr->end){
        posr = post;
    }
    
    if(!ignore){
        if(visited[posl->id][posr->id]){
            return 'X';
        }
        visited[posl->id][posr->id] = true;
        
        if(goal[posl->id][posr->id] != 'X'){
            return goal[posl->id][posr->id];
        }
    }
    
    
    
    for(char i = 'a'; i <= 'z'; i++){
        if(posl->children[i-'a']==NULL or posr->children[i-'a']==NULL){
            continue;
        }
        result.push_back(i);
        char o = vyries(pre,post,result,visited,goal,posl->children[i-'a'],posr->children[i-'a']);
        if(o != 'X'){
            return o;
        }
        result.pop_back();
    }
    
    return 'X';
    
}

int main(){
    int n;
    cin >> n;
    string words[n];
    for(int i = 0; i < n; i++){
        cin >> words[i];
    }
    
    trie_node *preroot,*postroot;
    preroot = new_node(NULL,0,0);
    postroot = new_node(NULL,0,0);
    preroot->id = 0;
    postroot->id = 0;
    int n1 = 1;
    int n2 = 1;
    
    for(int i = 0; i < n; i++){
        string word = words[i];
        
        n1 = save_word(preroot,word,false,0,n1);
        n2 = save_word(postroot,word,true,0,n2);
    }
    
    bool* visited[n1];
    char* goal[n1];
    for(int i = 0; i < n1; i++){
        visited[i] = new bool[n2];
        goal[i] = new char[n2];
        for(int j = 0; j < n2; j++){
            visited[i][j] = false;
            goal[i][j] = 'X';
        }
    }
    goal[0][0] = 'O';
    
    for(int i = 0; i < n; i++){
        string word = words[i];
        trie_node *left,*right;
        left = find_node(preroot,word,0);
        right = postroot;
        for(int j = word.length()-1; j >= 0; j--){
            left = left->parent;
            goal[left->id][right->id] = word[j];
            right = right->children[word[j]-'a'];
            if(j == 0){
                break;
            }
            goal[left->id][right->id] = 'O';
        }
    }
    
    
    vector<char> result;
    char o = vyries(preroot,postroot,result,visited,goal,preroot,postroot,true);
    
    if(o == 'X'){
        cout << -1;
    }else{
        for(int i = 0; i < result.size(); i++){
            cout << result[i];
        }
        if(o != 'O'){
            cout << o;
        }
        for(int i = result.size()-1; i >= 0; i--){
            cout << result[i];
        }
    }
    cout << endl;
    
    for(int i = 0; i < n1; i++){
        delete visited[i];
        delete goal[i];
    }
    
}