Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

Localhost

LCS - Implementação

Mensagens Recomendadas

Localhost

Para um problema recente da usaco, mais propriamente o Calf Flac, pesquisei e encontrei um técnica chamada Longest Common Substring. O que eu pensei foi inverter a string e encontrar o maior palindromo.

Eu implementei um pequeno exemplo aqui só para ver como é que isto funciona.

Alguém me podia ver se está bem implementado?

// LCS algorithm

#include <stdio.h>
#include <string.h>

#define MAX 24

int main(void) {
    char str1[] = "confuciussaymadamimadam";
    char str2[] = "madamimadamyassuicufnoc";
    char solved[1024];
    int table[MAX][MAX];
    int i,j;
    int longest = 0;
    for(i = 0; i < MAX; i++) {
        for(j = 0; j < MAX; j++) {
            table[i][j] = 0;
        }
    }
    for(i = 0; i < MAX; i++) {
        for(j = 0; j < MAX; j++) {
            if(str2[i] == str1[j]) {
                table[i + 1][j + 1] = table[i][j] + 1;
                if(table[i + 1][j + 1] > longest) {
                    longest = table[i + 1][j + 1];
                }
            }
        }
    }
    strncpy(solved,&str1[(strlen(str2)) - longest],longest);
    solved[longest] = '\0';
    printf("%s\n", solved);
    for(i = 0; i < MAX; i++) {
        for(j = 0; j < MAX; j++) {
            printf("%i | ", table[i][j]);
        }
        putchar('\n');
    }
    return 0;
}

Btw, adorei mesmo fazer este código.

EDIT: Já estive a calcular o tempo que esta approach me vai levar e é O(N * M) em Big-O.

N é a string toda, normal.

M é a string ao contrário sem os caracteres especiais.

O que faço é LCS e depois apartir da posição do longest percorro a string para trás Longest caracteres, o caontador de controlo não vai aumentar se não for uma letra do abcedário. E é isso.

EDIT: Estou agora a ler sobre suffix trees para ver se consigo resolver isto em tempo linear.  :)


here since 2009

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pcaldeira

Não vi se o código está bem implementado, mas vinha só sugerir que fosses tu a verificar isso :) Testar o programa é uma das capacidades mais importantes em concursos onde só tens o resultado no final, ou seja, após a submissão não tens qualquer feedback acerca dos pontos. Constrói vários casos de teste pequenos, para poderes verificar a resposta à mão, mas tenta cobrir todas as situações possíveis que o algoritmo possa encontrar.

Quanto ao problema, fizeste bem em pesquisar sobre ele, mas não tornes isso um hábito. Deves sempre tentar descobrir uma solução sozinho e só depois, se não tiveres mesmo nenhuma ideia, procurar ajuda. Eu fiz o mesmo que tu nalguns problemas do USACO, mas assim não estás a aproveitar ao máximo o programa de treino - o objectivo é ensinar-te a pensar, e não ensinar-te alguns algoritmos.

Já agora, eu no teu lugar não tentava implementar uma suffix tree por enquanto. É uma estrutura de dados demasiado complexa que aparece muito raramente em concursos (estive 3 anos envolvido nas ONI/IOI/concursos de secundário e nunca precisei de implementar uma, nem sei fazê-lo). Não digo que não seja bom tentares melhorar sempre as tuas soluções, mas como vais ler ou já leste num texto do USACO, em concursos deves usar sempre a ideia mais simples, desde que funcione.

Continua a treinar e boa sorte para as ONI!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Localhost

Eu já sei que o de cima está bem implementado. Aliás eu até já melhorei mas acabei por desistir dessa ideia. Já tenho uma ideia melhor para resolver este problema.

Eu procurei ajuda porque estava mesmo stucked :x

Podias era ajudar-me a ver se a minha ideia está certa  :)


here since 2009

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pcaldeira

Estou a ter TLE. Vou pensar!  :)

Mesmo que estejas a ter TLE, não precisas de solução linear para passar. Repara que o tamanho máximo do palíndromo está limitado no problema, e é muito mais pequeno que o tamanho da string. Podes explorar isso...

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Localhost

Era essa a ideia que eu estava a ter. Partir a string em M partes onde M é o tamanho do palindromo actual (este M vai decrescendo). No entanto vai haver uma altura, como no caso 2 em que a string é partida e em que não apanha o palindromo todo.

Tive outra ideia agora, vou tentar codar.


here since 2009

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Localhost

Parece que esta ideia que tive é mesmo para resultar. Estou a acabar  :)

EDIT: Já tenho a dar o maior palindromo, agora falta aqueles pormenores dos caracteres especiais e esta é uma parte um bocado complicada.


here since 2009

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
mogers

Suffix trees é complexo e algo que nunca precisei verdadeiramente. Quase sempre, podes optar por usar suffix arrays que são muito mais simples. Podes ler sobre isso em http://forums.topcoder.com/?module=Thread&threadID=627379&start=0&mc=15

Acho que esta matéria é menos importante do que as outras que se seguem na usaco.


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Localhost

Já vi vários posts pela web fora a dizer que sufix arrays e trees são muito importantes quando queremos resolver problemas com strings de uma maneira rápida e eficaz.

Pode-se resolver o Calf Flac com um sufix array?


here since 2009

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.