Trabalho Prático 2 - Menságens Assíncronas

Bonde, Tiago Bonde Um agente secreto brasileiro está neste momento em um grande perigo: Precisa desarmar uma bomba localizada diretamente abaixo do prédio do Departamento de Ciência da Computação (DCC) da UFMG. O vilão, Mário Traquina, é um velho conhecido da comunidade criptográfica: Ele sempre produz códigos para suas armadilhas com uma característica peculiar. Tal característica é que o código é sempre constituído por uma sequência de N cadeias de 10 letras minúsculas, S1, S2, S3…Sn. O plano de Mário é no futuro conseguir concatenar cadeias de sequências para dificultar cada vez mais a decodificação. No entanto, para que o código seja válido, a cadeia de sequência requer obediência a uma regra bastante fundamental: nenhuma cadeia da sequência pode ser subcadeia de uma concatenação de duas cadeias anteriores na sequência. Ou seja, o código não será válido se existirem 3 inteiros a,b e k tais que: ● 1 ≤ a < k ≤ N, 1 ≤ b < k ≤ N (a pode ser igual a b); e ● Sk é subcadeia da concatenação SaSb. Nosso agente secreto sabe que um código como S={aaaaaaabbb,yyuudiwwkl, kkfidaaooa} atende a regra de formação, mas que se adicionarmos a cadeia aooaaaaaaa no final da sequência, o código resultante S‘={aaaaaaabbb,yyuudiwwkl, kkfidaaooa, aooaaaaaaa}, será inválido, pois S‘4 é subcadeia da concatenação S‘3S‘1. A nossa tarefa, então, é ajudar o agente secreto a livrar a comunidade acadêmica de uma ameaça em potencial. Faremos isso ajudando a identificar se os códigos que ele está vendo são válidos ou não. Entrada A primeira linha da entrada contém um inteiro N, representando o número de cadeias na sequência. As N linhas seguintes contêm, cada uma, uma cadeia de 10 letras minúsculas, definindo a sequência de cadeias do código. Saída Seu programa deve imprimir uma linha contendo a cadeia "ok" caso o código seja válido, ou contendo a primeira cadeia na sequência que invalida o código. Quer dizer, contendo Sk onde k é o menor possível tal que Sk seja subcadeia de uma concatenação de duas cadeias anteriores na sequência. Restrições 1 ≤ N ≤ 10000 Exemplos Entrada 3 aaaaaaabbb yyuudiwwkl kkfidaaooa Saída ok Entrada 4 aaaaaaabbb yyuudiwwkl kkfidaaooa aooaaaaaaa Saída aooaaaaaaa Entrada 1 jfjshiddds Saída ok Entrada 2 abcdefghij abcdefghij Saída abcdefghij Entrada 8 xfwvijuydq hcprvezofg hwykagqawu givfzndqpy yvfiqgadfc wuhcprvezo qaswiksscl uchskpkcit Saída wuhcprvezo