Jump to content
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

Sign in to follow this  
Localhost

LCS - Implementação

Recommended Posts

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

Share this post


Link to post
Share on other 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!

Share this post


Link to post
Share on other 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

Share this post


Link to post
Share on other 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...

Share this post


Link to post
Share on other 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

Share this post


Link to post
Share on other 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

Share this post


Link to post
Share on other 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.

Share this post


Link to post
Share on other sites
Localhost

Tenho de começar a usar C++ mas a usaco parou-me nesse aspecto :x


here since 2009

Share this post


Link to post
Share on other 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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.