16

Estou a tentar fazer essa função com a ajuda das funções strcmp() e strncmp() e não estou a ter grande sucesso.

Imaginemos que tenho a string char s[] = "abc" e outra string char v[] = "cdeabf" , o output daria 0 (valor verdadeiro) pois os caracteres [a, b e c] pertencem a v. Caso contrário daria -1 (valor falso).

Se houver uma função pré-definida que me ajude, qual seria? E se der para fazer esta função sem ajuda de funções pré-definidas, como faria?

3
  • Você sabe o tamanho das strings? Dei uma resposta que não usa nenhuma função pré-definida exceto pela strlen (pois caso contrário não teria como saber qual o tamanho das strings). Mas se você já souber esses valores de antemão, aí não precisa...
    – mgibsonbr
    14/03/2015 às 12:54
  • 1
    @mgibsonbr embora eu tenha entendido a intenção do comentário tenho que dizer que é possível descobrir o tamanho da string sem uma função pré-definida, basta você escrever um código que faça exatamente o que a strlen faz :P Algo assim: const char *s; for (s = suaString; *s; ++s); int tamanho = s - suaString;. Só a título de curiosidade.
    – Maniero
    14/03/2015 às 13:24
  • @bigown haha é claro, falha minha! O que a strlen faz é justamente contar os caracteres até - mas sem incluir - o terminador nulo, facinho de fazer à mão se necessário... :P
    – mgibsonbr
    14/03/2015 às 14:00

5 Respostas 5

15
+100

Como referido por @mgibsonbr, a convenção C é 0 para falso, diferente de zero para verdadeiro.

Usando essa convenção, eu faria simplesmente:

...
return (strspn(s,aceitar) == strlen(s));

Edit: Explicação sumária: de acordo com o manual, capítulo das funções sobre strings:

$ man string.h 
....
size_t strspn(const char *s, const char *accept);
   Calculate the length of the starting segment in the string s that consists 
   entirely of bytes in accept.

temos uma função strspn (Ver detalhes aqui) que pode ajudar:

se todos os caracteres da string inicial estiverem na lista dos caracteres a aceitar, a função strspn(s,aceitar) devolverá o comprimento da string s (=todos).

Para a nossa questão, basta portanto comparar o número de caracteres aceites com strlen(s)


Obrigado ao @mgibsonbr pela ajuda com a explicação

14
  • 4
    Resposta excelente! Estou oferecendo uma recompensa pra ela. Contudo, seria desejável uma referência pra função strspn (exemplo), e talvez explicar o que ela faz.
    – mgibsonbr
    17/03/2015 às 18:13
  • 1
    Está muito boa a resposta @JJoao :). Obrigado pela explicação! ;) 17/03/2015 às 18:38
  • 2
    Acho que o @bigown tem razão, vejam no ideone
    – Jorge B.
    18/03/2015 às 15:55
  • 1
    @JorgeB. se for isto mesmo, e eu já tinha feito este teste, as pessoas estão votando em uma resposta errada que é facilmente verificável mas que ninguém se deu ao trabalho antes de votar. O voto deve ser dado quando você sabe que a solução é boa e funciona, não porque ela é curiosa.
    – Maniero
    18/03/2015 às 15:57
  • 1
    @JJoao será return (strspn(s,v) == strlen(s));?
    – Jorge B.
    18/03/2015 às 16:02
11

Não existe nada pronto mas(ver abaixo) não é difícil criar uma função que faça isto. Se entendi o que você deseja, seria isto:

#include <stdio.h>

int contem(char s1[], char s2[]) {
    for (int i = 0; s2[i]; i++) {
        int j;
        for (j = 0; s1[j]; j++) if(s2[i] == s1[j]) break;
        if (s1[j] == '\0') return 0;
    }
    return 1;
}

int main() {
    char s[] = "abc";
    char v[] = "cdeabf";
     if (contem(v, s)) printf("'%s' contém todos os caracteres presentes em '%s'", v, s);
     else printf("'%s' não contém todos os caracteres presentes em '%s'", v, s);
}

Veja funcionando no ideone. E no repl.it. Também coloquei no GitHub para referência futura.

Fica aí a solução para quem quer fazer na mão. Mas existe uma forma de alcançar o mesmo resultado conforme a resposta do JJoao. A função strspn retorna o tamanho da string sendo comparada se todos os caracteres estiverem presentes na outra string. Então fica fácil identificar o que se pede na pergunta. Usando função pronta ficaria assim:

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

int main() {
    char s[] = "abc";
    char v[] = "cdeabf";
    printf("'%s' %scontém todos os caracteres presentes em '%s'", v, (strspn(s, v) == strlen(s)) ? "" : "não ", s);
}

Veja funcionando no ideone. E no repl.it. Também coloquei no GitHub para referência futura.

5
  • Só não percebi uma coisa @bigown , qual o papel da variável j nesse caso? Obrigado pela resposta ;) 14/03/2015 às 13:17
  • @JoséCunha coloquei alguns comentário. O j é só a variável de controle do índice da string. Ele vai variando para andar caractere por caractere na string. Isto esclarece o que queria saber? Eu vi que você tinha aceitando minha resposta e depois trocou para a outra que fornece uma solução parecida, tanto que votei nela. Só fiquei na dúvida se você o fez porque depois viu que preferiu a outra ou foi sem querer e não percebeu que só pode aceitar uma resposta como a que mais ajudou você. Você poderá votar em todas as respostas e perguntas do site assim que tiver reputação suficiente.tour
    – Maniero
    14/03/2015 às 13:27
  • Obrigado pelo esclarecimento @bigown ;) Não sabia que se podia apenas aceitar uma resposta xD . De qualquer maneira , gostei muito dos comentários e da estrutura o que torna fácil a leitura! Obrigado pela Ajuda! ;) 14/03/2015 às 15:55
  • Não recomendo usar strlen dentro de loops, como você fez em if (j == strlen(s1)) {. strlen é uma operação cara, que leva tempo O(n) e nem sempre o compilador consegue ser esperto o suficiente para otimizá-la. No seu caso seria melhor usar s1[j] igual você já faz no for. Ou que sabe até trocar esses ifs e o break por um uso esperto de goto.
    – hugomg
    25/03/2015 às 0:52
  • @hugomg tem razão, fiz correndo e nem me preocupei com isto mas vou melhorar isto. Não quis usar o goto para não provocar ataques epiléticos em alguns programadores :D
    – Maniero
    25/03/2015 às 0:55
10

Como comparar caracteres é fácil (basta usar o operador de igualdade - ==), minha sugestão é simplesmente percorrer cada caractere de uma e da outra string verificando se eles são iguais:

// No cabeçalho:

#define VERDADEIRO 0
#define FALSO -1

// Na sua função:

int ts = strlen(s); // Tamanho da primeira string
int tv = strlen(v): // Tamanho da segunda string
for ( int i = 0 ; i < ts ; i++ ) { // Para cada caractere da primeira string
    char cs = ts[i]; // Esse caractere precisa aparecer em v
    int apareceu = FALSO; // No começo, não apareceu (pois ainda não começamos a buscar)
    for ( int t = 0 ; t < tv ; t++ ) { // Para cada caractere da segunda string
        char cv = tv[t]; // Esse caractere será comparado a cs
        if ( cs == cv ) { // Apareceu!
            apareceu = VERDADEIRO;
            break; // Para de testar a segunda string, pois já achou o caractere
        }
    }
    if ( apareceu == FALSO ) // Se continua FALSO, é porque não apareceu
        return FALSO;
}
return VERDADEIRO; // Se passou por todos os caracteres da primeira string e nenhum
                   // deles retornou FALSO, então é porque todos aparecem na segunda

Obs.: Defini VERDADEIRO como 0 e FALSO como -1, como estabelecido na pergunta, mas esse é um modo bem pouco usual de se representar esses valores; normalmente se usa 0 como falso e qualquer coisa diferente de 0 como verdadeiro. A menos que tenha uma boa razão para desviar dessa convenção, sugiro que não o faça.

2
  • Parece-me muito bom o código @mgibsonbr. Obrigado pelos comentários em cada passo. Ajuda imenso :) 14/03/2015 às 13:18
  • 2
    +1 pela observação acerca da convenção do C
    – JJoao
    17/03/2015 às 18:01
3

Atualização

Segue um outro modo alternativo sem o uso a função strchr:

int testarString(char *fonte, char encontrar[]){
    int i, ret = 0, tamanho = strlen(encontrar);
    while (*fonte){
        for (i = 0; i < tamanho; i++)
            ret += ((*fonte == encontrar[i]) ? 1: 0);
        *fonte++;
    }
    return ((ret == tamanho) ? 0: 1);
}

Exemplo funcional no Ideone.


Uma alternativa que pode ser utilizada é a função strchr, essa função retorna o ponteiro da primeira ocorrência de um caractere, ela recebe dois parâmetros, o primeiro é a string a ser percorrida, e o segundo, o caractere a ser encontrado.

A ideia é percorrer os caracteres da string a ser encontrada, no caso a variável s, e verificar se há correspondência na string a ser verificada, no caso, a variável v.

Isso pode ser implementado da seguinte forma:

int testarString(char fonte[], char encontrar[]){
    int i = 0;
    while (i <= strlen(encontrar)){
        if (strchr(fonte, encontrar[i]) == 0)
            return 1;
        i++;
    }
    return 0;
}

Exemplo funcional no Ideone.

2

Uma solução mais eficiente para esse problema involve ordenar as strings antes de começar a compará-las. Em pseudo código;

ss = sort(s) // "acb" vira "abc"
sv = sort(v) // "cdeabf" vira "abcdef"

//invariante: Os caracteres de ss[0,i) estão contidos em sv[0,j)
i = j = 0
while i < len(ss) do
    while j < len(sv) and ss[i] != sv[j] do
        j += 1
    done
    if j < len(sv) then
        i += 1  // achei um par para ss[i]
    else
        return NAO // ss[i] não tem par em v
    end
done

return SIM

A maioria das outras respostas apresentam algoritmos quadráticos, que levam um tempo proporcional ao tamanho de uma string mumltiplicado pelo tamanho da outra. O algoritmo que apresentei consiste em uma etapa de ordenação que leva tempo O(n log n) (ou O(n) se você usar um radix-sort da vida) seguida de uma etapa de comparação O(n) que faz apenas uma passada nas strings.

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 .