Este artigo resolve o problema Rima, que consiste em construir a sequência mais longa de palavras onde cada par adjacente rima. A definição de rima é que o comprimento do sufixo comum mais longo entre duas palavras A e B deve ser pelo menos max(|A|, |B|) - 1.

Descrição do Problema

Dado N palavras distintas, todas compostas por letras minúsculas, com o comprimento total não excedendo 3×10^6, encontre o comprimento máximo de uma sequência em que palavras ajdacentes rimam.

Formato de Entrada:

• A primeira linha contém um inteiro N (1 ≤ N ≤ 5×10^5).
• As próximas N linhas contêm uma string cada.

Formato de Saída:

• Um inteiro representando o comprimneto máximo da sequência.

Exemplos

Exemplo 1:

Entrada:
4
honi
toni
oni
ovi

Saída: 3

Exemplo 2:

Entrada:
5
ask
psk
krafna
sk
k

Saída: 4

Exemplo 3:

Entrada:
5
pas
kompas
stas
s
nemarime

Saída: 1

Solução com Árvore Trie e DP em Árvore

Como o problema envolve sufixos comuns, inserimos cada palavra invertida em uma árvore Trie. Isso permite manipular os sufixos eficientemente. Na Trie, dois nós de término (representando finais de palavras) que rimam estão em relação pai-filho ou irmão-irmão.

Usamos programação dinâmica em árvore para calcular a sequência mais longa. Definimos:

• f[u]: o número máximo de palavras que podem ser adicionadas após a palavra representada pelo nó u, considerando apenas um lado (ou seja, apenas palavras que rimam com u e estão abaixo na Trie).
• ans: a resposta global, calculada combinando os maiores valores de f em diferentes subárvores.

A transição de estado considera os filhos de um nó u. Para cada filho v, se v é um nó de término, ele pode ser conectado. A ideia é pegar os dois maiores valores de f[v] entre os filhos e adicionar o número de outros filhos de término válidos.

Implementação

O código a seguir implementa a solução em C++. As variáveis e estruturas foram renomeadas para maior clareza, mantendo a correção.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_NODES = 5000010;
const int ALPHABET_SIZE = 26;

int trie[MAX_NODES][ALPHABET_SIZE];
bool is_terminal[MAX_NODES];
int dp_value[MAX_NODES];
int global_max = 0;
int node_count = 1; // Nó raiz é 1

void insert_word(const string& word) {
    int current = 1;
    for (int i = word.length() - 1; i >= 0; --i) {
        int index = word[i] - 'a';
        if (!trie[current][index]) {
            trie[current][index] = ++node_count;
        }
        current = trie[current][index];
    }
    is_terminal[current] = true;
}

void dfs(int node) {
    int child_terminals = 0;
    pair<int, int> max_two = {0, 0}; // Armazena os dois maiores dp_value entre filhos

    for (int i = 0; i < ALPHABET_SIZE; ++i) {
        int child = trie[node][i];
        if (child) {
            if (is_terminal[child]) {
                child_terminals++;
            }
            dfs(child);
            // Atualizar os dois maiores valores de dp_value
            if (dp_value[child] > max_two.first) {
                max_two.second = max_two.first;
                max_two.first = dp_value[child];
            } else if (dp_value[child] > max_two.second) {
                max_two.second = dp_value[child];
            }
            dp_value[node] = max(dp_value[node], dp_value[child]);
        }
    }

    if (is_terminal[node]) {
        dp_value[node] += max(1, child_terminals);
    } else {
        dp_value[node] = 0;
    }

    // Atualizar a resposta global combinando os dois maiores caminhos
    int candidate = max_two.first + max_two.second + max(0, child_terminals - 2);
    global_max = max(global_max, (is_terminal[node] ? 1 : 0) + candidate);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<string> words(n);
    for (int i = 0; i < n; ++i) {
        cin >> words[i];
        insert_word(words[i]);
    }

    dfs(1);
    cout << global_max << endl;

    return 0;
}

O algoritmo executa em tempo linear em relação ao comprimento total das palavras, tornando-o eficiente para os limites do problema.