0

Estou aqui com um problema nesta função int supre (char s1[ ], char s2[ ]) , que calcula o tamanho do maior sufixo de s1 que é prefixo de s2. Por exemplo se tiver supre ("batota" , "totalidade") deve retornar 4, uma vez que a string "tota" é sufixo de "batota" que é prefixo de "totalidade".

Tentei fazer esta função com o auxilio da função strrev ( ) para comparar carater a carater , mas não deu grande sucesso ..

Se houver alguma função que me ajude , qual devo usar? E é possivel fazer sem ajuda de funções auxiliares?

3
  • 3
    Coloque o que você já fez para a gente ter uma ideia do que está tentando fazer. Mesmo que tenha problemas e esteja incompleto.
    – Maniero
    Commented 21/03/2015 às 15:56
  • 1
    eu fazia uma solução tipo recursiva que vai testando substrings de s1 cada vez mais pequenas: eg ... 1) "batota" não é sufixo de "totalidade" 2) "atota" não é sufixo de "totalidade" 3) "tota" é sufixo de "totalidade"
    – pmg
    Commented 21/03/2015 às 16:21
  • @OP, você deseja uma maneira para resolver o problema ou quer dicas para resovê-lo?
    – user2692
    Commented 10/04/2015 às 20:28

1 Resposta 1

2

Esse é um porbleminha que embora simples, não tem mágica pra resolver: é um algoritmo simples, que a gente consegue pensar e entender como resolver "manualmente" - e o caminho é entender o algoritmo, e depois transcrever para C.

Você tem um conjunto de ferramentas que são as funções par amanipulação de string da biblioteca padrão do C,e a verificação direta dos caractéres. Você também pode escrever suas funções se não houver alguma.

Mas então - perceba que é um algoritmo em "etapas" - não é uma coisa de 3 ou 4 linhas - por que você vai ter que no mínimo achar o ponto inícial de busca, e comparar os caracteres a partir dali.

Então, o pseudo-algoritmo em portugues, poderia começar assim:

  • prepare uma string vazia de resposta S3.
  • achar se há,e a posição N do primeiro caractere de S2 dentro de S1;
  • Se não houver N, retorne dizendo que o sufixo é a string vazia
  • crie um contador i = 0;
  • checkpoint
  • copie o caractere S1[N] para a string de resposta S3
  • Incremente o valor de i
  • se o caractere em S1[N+i] é o final da string (caractere '\x00') - a resposta é o que temos em S3: acresente um mcarcador de final de string em S3 e retorne S3 (faça o mesmo se chegou ao final de S2)
  • compare o caractere N + i em S2 com o caractere na posição (0 + i) de S2;
  • se são diferentes, zere a string S3, e retorne um sufixo vazio (** mas veja a nota abaixo)
  • retorne para "checkpoint"

Poronto -agora você traduz isso para "C" - e perceba que na descriçao em portugues surge naturalmente o que será um laço "for" ou "while' em linguagem de programação.

** - ha uma pegadinha nesse algoritmo aí - se a primeira letra da segunda palavra ocorrer mais de uma vez na primeira palavra, a descrição acima não dá conta. (por exemplo: "batota", e "tarifa" - ele vai achar o primerio "t" de "batota", mas vai parar a busca no "o" - quando o sufixo está após o segundo "t") - ou você repete a busca por "t", ou- pra começar tudo, procura pela primeira letra de S2 em S1, mas da direita para a esquerda - essa segunda alternativa é muito mais fácil, mas acho que você não terá uma função pronta na stdlib de C para isso - então vai fazer sua própria funçãozinha pra isso (acredite, vale a pena):

  • procure pela letra X em S1 a partir do final:
  • faça i igual o comprimento total de S1
  • heckpoint`verifique se o caractere S1[i] é X - se sim, retorne i
  • decremente i
  • se i for menor que zero, retorn i (e aproveite o retorno de -1 como indicação de que a letra não existem em S1)
  • vá para checkpoint

--Pronto agora você já tem onde começar. Não é o propóstio do S.O. dar respostas prontas - então tente traduzir isso para C.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .