Test if all characters in the first string also appear in the second

16

I'm trying to do this function with the help of the functions strcmp() and strncmp() and I'm not having great success.

Let's say that I have the string char s[] = "abc" and another string char v[] = "cdeabf" , the output would give 0 (true value) since the characters [ a , b and c ] belong to v . Otherwise it would give -1 (false value).

If there is a predefined function to help me, what would it be? And if you can do this function without the help of predefined functions, how would you do it?

    
asked by anonymous 14.03.2015 / 13:36

5 answers

11

There is nothing ready but (see below) it is not difficult to create a function that does this. If I understood what you wanted, it would be this:

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

int contem(char s1[], char s2[]) {
    int j;
    for (int i = 0; s2[i]; i++) {
        for (j = 0; s1[j]; j++) {
            if(s2[i] == s1[j]) {
                break;
            }
        }
        if (s1[j] == '
#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);
    return 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); } return 0; }

See working on ideone .

Here's the solution for anyone who wants to do it. But there is a way to achieve the same result as the JJao's response. The function strspn returns the size of the string being compared if all the characters are present in the other string . So it is easy to identify what is asked in the question. Using ready-made function would look like this:

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

int contem(char s1[], char s2[]) {
    int j;
    for (int i = 0; s2[i]; i++) {
        for (j = 0; s1[j]; j++) {
            if(s2[i] == s1[j]) {
                break;
            }
        }
        if (s1[j] == '
#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);
    return 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); } return 0; }

See working on ideone .

    
14.03.2015 / 14:10
15

As referred by @mgibsonbr, convention C is 0 for false, non-zero for true.

Using this convention, I would simply do:

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

Edit: Summary Explanation : According to the manual, strings functions chapter:

$ 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.

We have a strspn ( View details here ) function that can help:

If all the characters of the initial string are in the list of characters to accept, the function strspn(s,aceitar) will return the length of the string s (= all).

For our question, it is therefore enough to compare the number of accepted characters with strlen(s)

Thanks to @mgibsonbr for help with the explanation

    
17.03.2015 / 19:01
10

How to compare characters is easy (just use the equality operator - == ), my suggestion is to simply go through each character of one and the other string checking if they are the same:

// 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

Note: Define VERDADEIRO as 0 and FALSO as -1 , as stated in the question, but this is a very unusual way to represent these values; 0 is normally used as false and anything other than 0 is true. Unless you have good reason to deviate from this convention, I suggest you do not.

    
14.03.2015 / 13:53
3

Update

Follow another alternative without using 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);
}

Functional example on Ideone .

An alternative that can be used is the strchr function, this function returns the first occurrence of a character, it receives two parameters, the first is the string to be traversed, and the second, the character to be found.

The idea is to go through the characters of the string to be found, in this case the variable s , and check for matching string to be checked, in case , the variable v .

This can be implemented as follows:

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

Functional example in Ideone .

    
18.03.2015 / 15:47
2

A more efficient solution to this problem involves sorting the strings before beginning to compare them. In pseudo code;

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
Most of the other answers present quadratic algorithms, which take a time proportional to the size of a string multiplied by the size of the other. The algorithm I presented consists of a sort step that takes time O (n log n) (or O (n) if you use a life radix-sort) followed by a comparison step O (n) that does just one pass in the strings.

    
25.03.2015 / 01:45