Código (OBI - 2017)

codigo.cpp

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 10;

struct node
{
	node* b[26];

	bool fim = false;
};


void add(node* rt, string const& s)
{
	node* at = rt;
	for(auto u : s)
	{
		if(!at -> b[u - 'a']) at -> b[u - 'a'] = new node();
		at = at -> b[u - 'a'];
	}
	at -> fim = true;
}

bool find(node* rt, string const& s)
{
	node* at = rt;

	if((int)s.size() == 0) return false;
	
	for(auto u : s)
	{
		if(!at -> b[u - 'a']) return false;
		at = at -> b[u - 'a'];
	}
	return at -> fim;
}



int main()
{
	node* suffix = new node();
	node* preffix = new node();

	int n;

	cin >> n;

	vector<string> s;

	for(int i = 0; i < n; i++)
	{
		string st;
		cin >> st;
		s.push_back(st);
	}


	for(int i = 0; i < n; i++)
	{
		string st = s[i];
		add(suffix, st);
		for(int j = 0; j < 10; j++)
		{
			string pref, suf;

			for(int k = 0; k <= j; k++)
			{
				pref += st[k];
			}
			for(int k = j + 1; k < 10; k++)
			{
				suf += st[k];
			}
			if(find(preffix, st))
			{
				cout << st << "\n";
				return 0;
			}
			if(find(suffix, pref) and find(preffix, suf))
			{
				cout << st << "\n";
				return 0;
			}
			
			add(suffix, suf);
			add(preffix, pref);
		}
	}

	cout << "ok\n";


}