PLAGIO

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

Plágio Musical (http://br.spoj.com/problems/PLAGIO/)

Problema

Dada uma sequência de notas de uma música e um trecho de outra música (que é suspeito de ter sido plagiado), dizer se o trecho aparece na música, de forma idêntica ou com um deslocamento fixo (ou seja, as mesmas notas em outro tom). O problema explica todos os conceitos musicais necessários para sua resolução.

Observações

  • O que importa não são as notas em si, mas os intervalos entre as notas consecutivas. Transforme as sequências dadas para refletir isto.
  • O problema parece com o de busca em strings de caracteres. Mas note que podemos interpretar sequências de inteiros como strings da mesma forma como fazemos com caracteres, e aplicar os mesmos algoritmos.

Solução

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

Primeiro, precisamos codificar as notas de uma forma mais conveniente. Podemos, por exemplo, transformá-las em inteiros de $0$ a $11$, em que a nota $C$ é o inteiro $0$ e a nota $B$ é o inteiro $11$ (ou você pode começar do $A$; começar do $C$ seria mais natural para um músico).

Depois, para nos livrar dos tons diferentes em que o trecho suspeito pode ocorrer na música, basta construírmos o array de diferenças tanto da música quanto do trecho. Ou seja, para cada um dos dois, criamos um array com um elemento a menos, e o i-ésimo elemento do array de diferença é a diferença entre os elementos $i$ e $i+1$ do array original.

Note que o que queremos saber é exatamente se o array de diferenças do trecho ocorre no array de diferenças da música. Se isto acontece, em algum tom, o trecho ocorre na música.

Para tal, podemos usar os algoritmos de busca em strings. O KMP, por exemplo, ensinado num tutorial do TopCoder, resolve este problema em tempo $O(M + T)$, o que é bastante eficiente para este problema. Note que o algoritmo naïve, que tem complexidade $O(MT)$, não passa no tempo limite.

Implementação

As dicas de implementação ficam ocultas por padrão. Desencorajamos que você as olhe antes de ter tentado.

Basicamente, para adaptar sua implementação do KMP de strings para vetores de inteiros, você só trocará tipos de variáveis, e não deverá ter dificuldades para tal.

Ferramentas pessoais
Espaços nominais

Variantes
Ações
Navegação
Ferramentas