Cultivando strings (Growing Strings): dois caminhos

Mais um problema interessante, da ACM/ICPC South America, do contest de 2010! O problema é Cultivando Strings (ou Growing Strings, em inglês), e vou (tentar :) ) resolver por duas formas diferentes: o algoritmo de Aho-Corasick e Suffix Arrays.

URI 1141 - Cultivando Strings / Growing Strings (link)

(A partir daqui, vou supor que você conhece os métodos. Se não for o caso, google it! Se algum dia eu escrever alguma coisa sobre um dos dois, edito o link aqui).

Traduzindo o problema: são várias strings (1 < N < 10^4) que somam no máximo 10^6 letras. Queremos achar a maior sequência de strings que se encaixam.

Podemos fazer uma analogia com um problema de grafo. Se uma palavra está contida em outra, há uma aresta direcional ligando-as, sem ciclos. Para o primeiro exemplo da entrada, teríamos o grafo acima. Ordenar pelo tamanho facilita as coisas, porque, obviamente, as arestas só vão da direita para esquerda.

Definimos (int) subseq[i], i de 1 a N, como o tamanho da maior sequência que termina na i-ésima string. É fácil ver que subseq[K] é o maior valor de {subseq[i] + 1, tal que existe um aresta de i para K}. A resposta é {maior valor de subseq[K], 1 < K < N}. O vetor do primeiro exemplo está aqui embaixo.

O problema é: como descobrir quais strings estão contidas em quais? Podemos testar para cada string i, qual string j está contida, mas essa solução seria O(N^2) = 10^8.

1) Aho-Corasick

Com o algoritmo de Aho-Corasick, não é difícil. Esta animação muito boa vai te dar uma noção (link).

Adicionamos as palavras por ordem de tamanho (menor para maior), cada nó é uma letra e se uma letra é o fim de uma palavra (digamos da palavra i), marcamos o nó com fim = i. Se não, fim = -1.

A medida que adicionamos as palavras, também testamos ela como entrada no Aho-Corasick, e conseguimos achar todos os matches de palavras que já estão no dicionário em O(tamanho da string + número de matches). Iterativamente, preenche-se o vetor subseq[]. Como palavras menores são adicionadas primeiro, todos os matches são achados, totalizando O(soma das strings + matches).

2) Suffix Array

A solução com suffix array é um pouco mais trabalhosa. Só consegui passar no tempo com um suffix array O(N) (que retirei daqui: link, observe a condição inicial).

A ideia é simples. Checamos no suffix array todas as posições de começo de palavra, e avaliamos o lcp array para ver se há matches acima ou abaixo da string (enquanto lcp[pos] >= tamanho da palavra, há match). Ou seja, para cada palavra, checamos em quais outras ela está contida.

 

Para isso, precisamos: dos vetores sa, ra e lcp do suffix array; saber onde começa cada palavra (marcamos em um vetor); e ainda, dado uma letra, a que palavra ela pertence (já que no suffix array, as palavras estão concatenadas em uma única).

Fazendo esse procedimento da menor para a maior palavra, preenchemos o vetor subseq[] iterativamente.

int l; //numero de letras no suffix array

struct word {
  int ini, len;
};
word v[10005];

bool comp(const word &a, const word &b) {
  return a.len < b.len;
}

int main()
{
  int N, answer;
  while(scanf("%d", &N) != EOF && N) {
    memset(text, 0, sizeof(text));
     
    l = 0;
    FOR(K, N) {
      scanf(" %s", text+l);
      v[K].ini = l;
      v[K].len = strlen(text+l);
      FOR(contador, v[K].len+1) {
        currentString[l] = K;
        l++;
      }
    }
    sort(v, v+N, comp);
    suffixArray(...);
    LCP(...);

    //Suffix array: int sa[MAXN], ra[MAXN], lcp[MAXN]
    //char text[MAXN]
 
    //Zera o vetor subseq[] 
    memset(subseq, 0, sizeof(subseq));
    answer = 0;

    FOR(K, N) {
      int tmp = RA[v[K].ini];
      // tmp eh o ponteiro que percorre o suffix array
          
      if(subseq[currentString[v[K].ini]] == 0)
        subseq[currentString[v[K].ini]] = 1;
      if(subseq[currentString[v[K].ini]] > answer)
        answer = subseq[currentString[v[K].ini]];

      //Checa os matches para cima
      while(tmp > 0 && lcp[tmp] >= v[K].len) {
        if(subseq[currentString[sa[tmp-1]]] <
             subseq[currentString[v[K].ini]] + 1) {
          subseq[currentString[sa[tmp-1]]] =
             subseq[currentString[v[K].ini]] + 1;
        }
        tmp--;
      }

      tmp = RA[v[x].ini];
      //Checa os matches para baixo
      while(tmp < n && lcp[tmp+1] >= v[K].len) {
        if(subseq[currentString[sa[tmp+1]]] <
              subseq[currentString[v[K].ini]] + 1) {
          subseq[currentString[sa[tmp+1]]] =
              subseq[currentString[v[K].ini]] + 1;
        }
        tmp++;
      }
    }
    printf("%d\n", answer);
  }
  return 0;
}

OBS: Fiz uma solução para os dois métodos, e com Aho-Corasick foi 10x mais rápido :)