FINDSR

De DCC UFMG - Maratona de Programação
Ir para: navegação, pesquisa

Find String Roots (http://spoj.com/problems/FINDSR/)

Problema

Dada uma string $s$, determinar o maior $n$ tal que $s$ possa ser obtida através da concatenação de uma string qualquer $b$ consigo mesma $n$ vezes.

Observações

Note que nem todo $n$ é possível para certos tamanhos de $s$. Por exemplo, se $s$ tem tamanho ímpar, é impossível obtê-la através da concatenação de uma string consigo mesma duas vezes, pois isto teria sempre como resultado uma string de tamanho par.

Dicas

  • Você consegue determinar, para um dado $n$ fixo, se $s$ é a justaposição de uma string $n$ vezes?
  • Agora tente determinar, para um dado $|s|$, o que caracteriza os possíveis valores de $n$.
  • Uma outra solução (mais eficiente, inclusive) consiste em examinar cuidadosamente uma parte do algoritmo KMP.

Solução

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.

Suponha que seja possível obter $s$ através de $n$ repetições da string $b$. O tamanho da string resultante de $n$ repetições de $b$ é $n \times |b|$, e sabemos que isto é igual a $s$. Ou seja,

$$|s| = n \times |b|$$

O que significa que n necessariamente é um divisor de $|s|$. Agora, podemos testar todos os divisores $d$ de $n$, verificando, para cada um, se $s$ é a repetição de uma certa string $d$ vezes.

Isto é eficiente porque os números até $10^5$ não têm muitos divisores. O número menor que $10^5$ com maior número de divisores tem menos de $150$ divisores.

Assim, escolhemos o maior $d$ encontrado para o qual $s$ é a repetição de uma string $d$ vezes. Falta determinar, dado um $d$ fixo, se $s$ é ou não a repetição de uma certa string $d$ vezes.

Este, porém, é um problema simples. A tal string obviamente deve ter tamanho $\frac{|s|}{d}$. Assim, esta string é exatamente o prefixo de $s$ de tamanho $\frac{|s|}{d}$, se ela existir. Agora, basta verificar se todo caractere de $s$ é equivalente ao seu caractere correspondente na string base (o prefixo de $s$). Ou seja, verificar se $s_i = s_{(i \mod d)},\ \forall i \in [0, |s|]$.

Assim, nossa solução tem complexidade $O(|s| * \sigma(s))$, onde $\sigma(n)$ é o número de divisores de $n$.

Curiosidade: há uma solução de tempo $O(|s|)$ para este problema. Ela se baseia na função prefixo ($\pi$) calculada no algoritmo KMP. $\pi_s(x)$ é o tamanho do maior sufixo próprio de $s_{0..x}$ que também é prefixo de $s_{0..x}$. Esta função prefixo é calculada para todos os caracteres do padrão em $O(|s|)$.

Suponha agora que $\pi_s(|s|-1) = k$, ou seja, o maior sufixo próprio de $s$ que também é prefixo de $s$ tem tamanho $k$. O que isto significa? Observemos os primeiros $|s| - k$ caracteres de $s$. Eles são tanto prefixos de $s$ (obviamente) quanto prefixos do sufixo de tamanho $k$ de $s$, já que $s_{0..k}$ = $s_{(|s| - k)..|s|}$ (é o que representa $\pi_s(|s|-1) = k$). Ou seja, o prefixo de $s$ de tamanho $2 \times (|s| - k)$ é a repetição da substring $s_{0..(|s| - k)}$. Mas aplicando o mesmo raciocínio indutivamente, chegaremos à conclusão de que $s$ é uma string obtida pela repetição do seu prefixo de tamanho $|s| - k$! Pode ser difícil enxergar este fato, mas você verá que é verdade (basta realmente aplicar o mesmo raciocínio, usando sempre o caso anterior, para concluir que os prefixos de $s$ de tamanho $3 \times (|s| - k)$, $4 \times (|s| - k)$, e daí em diante, são repetições do prefixo de tamanho $|s| - k$).

Assim, o expoente $N$ da solução é $\frac{|s|}{|s| - k}$. Como $k$ pode ser encontrado em tempo $O(|s|)$, a complexidade desta solução é linear no tamanho da string de entrada.

Implementação

As dicas de implementação ficam ocultas por padrão. Desencorajamos que você as olhe antes de ter tentado.
A implementação da solução não deve ser difícil. Note que, embora você possa obter os divisores de $|s|$ de várias formas, como $|s|$ é relativamente pequeno, basta percorrer todos os números de $|s|$ até $1$ e fazer o teste descrito na solução sempre que encontrar um divisor.
Ferramentas pessoais
Espaços nominais

Variantes
Ações
Navegação
Ferramentas