Jump to: navigation, search

The C Programming Language, 2nd Edition, by Kernighan and Ritchie
Exercise 2.05 on page 48

Write the function any(s1,s2) , which returns the first location in the string s1 where any character from the string s2 occurs, or -1 if s1 contains no characters from s2 . (The standard library function strpbrk does the same job but returns a pointer to the location.)



Solution by Vidhan Gupta

/* Write the function any (s1, s2), which returns the first location in the string s1
where any character from the string s2 occurs, or -1 if s1 contains no characters from s2.
(The standard library function strpbrk does the same job but returns a pointer to the locaiton.) */

#include <stdio.h>

int any(char s1[], char s2[]);

int main()
{
    char s1[] = "Hello I'm a programmer";
    printf("%d\n", any(s1, "mmer"));
    return 0;
}

int any(char s1[], char s2[])
{
    int i, j;

    for (i = 0; s2[i] != '\0'; i++)
    {
        for (j = 0; s1[j] != '\0'; j++)
            if (s1[j] == s2[i])
                return j;
    }

    return -1;
}

OUTPUT:
8

Solution by Richard Heathfield

Here is my solution, which is very simple but quite naive and inefficient. It has a worst-case time complexity of O(nm) where n and m are the lengths of the two strings. 

/*
 * Exercise 2-5 Page 48
 *
 * Write the function any(s1,s2), which returns the first location
 * in the string s1 where any character from the string s2 occurs,
 * or -1 if s1 contains no characters from s2. (The standard library
 * function strpbrk does the same job but returns a pointer to the
 * location.) 
 *
 */

int any(char s1[], char s2[])
{
  int i;
  int j;
  int pos;

  pos = -1;

  for(i = 0; pos == -1 && s1[i] != '\0'; i++)
  {
    for(j = 0; pos == -1 && s2[j] != '\0'; j++)
    {
      if(s2[j] == s1[i])
      {
        pos = i;
      }
    } 
  }

  return pos;
}

/* test driver */

/* We get a helpful boost for testing from the question text, because we are
 * told that the function's behaviour is identical to strpbrk except that it
 * returns a pointer instead of a position. We use this fact to validate the
 * function's correctness.
 */

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

int main(void)
{
  char *leftstr[] =
  {
    "",
    "a",
    "antidisestablishmentarianism",
    "beautifications",
    "characteristically",
    "deterministically",
    "electroencephalography",
    "familiarisation",
    "gastrointestinal",
    "heterogeneousness",
    "incomprehensibility",
    "justifications",
    "knowledgeable",
    "lexicographically",
    "microarchitectures",
    "nondeterministically",
    "organizationally",
    "phenomenologically",
    "quantifications",
    "representationally",
    "straightforwardness",
    "telecommunications",
    "uncontrollability",
    "vulnerabilities",
    "wholeheartedly",
    "xylophonically",
    "youthfulness",
    "zoologically"
  };
  char *rightstr[] =
  {
    "",
    "a",
    "the",
    "quick",
    "brown",
    "dog",
    "jumps",
    "over",
    "lazy",
    "fox",
    "get",
    "rid",
    "of",
    "windows",
    "and",
    "install",
    "linux"
  };

  size_t numlefts = sizeof leftstr / sizeof leftstr[0];
  size_t numrights = sizeof rightstr / sizeof rightstr[0];
  size_t left = 0;
  size_t right = 0;

  int passed = 0;
  int failed = 0;

  int pos = -1;
  char *ptr = NULL;

  for(left = 0; left < numlefts; left++)
  {
    for(right = 0; right < numrights; right++)
    {
      pos = any(leftstr[left], rightstr[right]);
      ptr = strpbrk(leftstr[left], rightstr[right]);

      if(-1 == pos)
      {
        if(ptr != NULL)
        {
          printf("Test %d/%d failed.\n", left, right);
          ++failed;
        }
        else
        {
          printf("Test %d/%d passed.\n", left, right);
          ++passed;
        }
      }
      else
      {
        if(ptr == NULL)
        {
          printf("Test %d/%d failed.\n", left, right);
          ++failed;
        }
        else
        {
          if(ptr - leftstr[left] == pos)
          {
            printf("Test %d/%d passed.\n", left, right);
            ++passed;
          }
          else
          {
            printf("Test %d/%d failed.\n", left, right);
            ++failed;
          }
        }
      }
    }
  }
  printf("\n\nTotal passes %d, fails %d, total tests %d\n",
         passed,
         failed,
         passed + failed);
  return 0;
}

Solution by Partha Seetala

Here's a much better solution, by Partha Seetala. This solution has a worst- case time complexity of only O(n + m) which is considerably better.

It works in a very interesting way. He first defines an array with one element for each possible character in the character set, and then takes the second string and 'ticks' the array at each position where the second string contains the character corresponding to that position. It's then a simple matter to loop through the first string, quitting as soon as he hits a 'ticked' position in the array. 

#include <stdio.h> /* for NULL */

int any(char *s1, char *s2) 
{
        char array[256]; /* rjh comments
                          * (a) by making this char array[256] = {0}; the first loop becomes unnecessary.
                          * (b) for full ANSIness, #include <limits.h>, make the array unsigned char,
                          *     cast as required, and specify an array size of UCHAR_MAX + 1.
                          * (c) the return statements' (parentheses) are not required.
                          */
        int  i;
        if (s1 == NULL) {
                if (s2 == NULL) {
                        return(0);
                } else {
                        return(-1);
                }
        }

        for(i = 0; i < 256; i++) {
                array[i] = 0;
        }
        
        while(*s2 != '\0') {
                array[*s2] = 1;
                s2++;
        }

        i = 0;
        while(s1[i] != '\0') {
                if (array[s1[i]] == 1) {
                        return(i);
                }
                i++;
        }
        return(-1);
}

/* test driver by Richard Heathfield */

/* We get a helpful boost for testing from the question text, because we are
 * told that the function's behaviour is identical to strpbrk except that it
 * returns a pointer instead of a position. We use this fact to validate the
 * function's correctness.
 */

#include <string.h>

int main(void)
{
  char *leftstr[] =
  {
    "",
    "a",
    "antidisestablishmentarianism",
    "beautifications",
    "characteristically",
    "deterministically",
    "electroencephalography",
    "familiarisation",
    "gastrointestinal",
    "heterogeneousness",
    "incomprehensibility",
    "justifications",
    "knowledgeable",
    "lexicographically",
    "microarchitectures",
    "nondeterministically",
    "organizationally",
    "phenomenologically",
    "quantifications",
    "representationally",
    "straightforwardness",
    "telecommunications",
    "uncontrollability",
    "vulnerabilities",
    "wholeheartedly",
    "xylophonically",
    "youthfulness",
    "zoologically"
  };
  char *rightstr[] =
  {
    "",
    "a",
    "the",
    "quick",
    "brown",
    "dog",
    "jumps",
    "over",
    "lazy",
    "fox",
    "get",
    "rid",
    "of",
    "windows",
    "and",
    "install",
    "linux"
  };

  size_t numlefts = sizeof leftstr / sizeof leftstr[0];
  size_t numrights = sizeof rightstr / sizeof rightstr[0];
  size_t left = 0;
  size_t right = 0;

  int passed = 0;
  int failed = 0;

  int pos = -1;
  char *ptr = NULL;

  for(left = 0; left < numlefts; left++)
  {
    for(right = 0; right < numrights; right++)
    {
      pos = any(leftstr[left], rightstr[right]);
      ptr = strpbrk(leftstr[left], rightstr[right]);

      if(-1 == pos)
      {
        if(ptr != NULL)
        {
          printf("Test %d/%d failed.\n", left, right);
          ++failed;
        }
        else
        {
          printf("Test %d/%d passed.\n", left, right);
          ++passed;
        }
      }
      else
      {
        if(ptr == NULL)
        {
          printf("Test %d/%d failed.\n", left, right);
          ++failed;
        }
        else
        {
          if(ptr - leftstr[left] == pos)
          {
            printf("Test %d/%d passed.\n", left, right);
            ++passed;
          }
          else
          {
            printf("Test %d/%d failed.\n", left, right);
            ++failed;
          }
        }
      }
    }
  }
  printf("\n\nTotal passes %d, fails %d, total tests %d\n",
         passed,
         failed,
         passed + failed);
  return 0;
}

Solution by Amarendra Godbole

This solution builds on the code snippets shown in the book. -Amarendra Godbole 

int
any(char s[], char t[]) {
    int i, j, k, pos = -1;

    for (k = 0; t[k] != '\0'; k++) {
        for (i = j = 0; s[i] != '\0'; i++) {
            if (s[i] == t[k]) {
                if (pos == -1)
                    pos = i;
                else
                    if (i < pos)
                        pos = i;
            }
        }
    }
    return pos;
}

Solution by Pilcrow

Could anything be simpler? 

int any(char s1[], char s2[])
{
	int i, j;

	for(i = 0; s1[i] != '\0'; i++) {		/* for each s1[i] */
		for(j = 0; s2[j] != '\0'; j++) {	/* for each s2[j] */
			if(s1[i] == s2[j]) 		/* match found? */
				return i;		/* no need for further code */
		}
	}
	return -1;					/* no match */
}

Solution by Jrun

#include <stdio.h>

int any(char s1[],char s2[]);

int main() {
  char s1[] = "hello world";
  char s2[] = "pjwyh";
  printf("%d\n", any(s1,s2));
  return 0;
}

int
any(char s1[], char s2[]) {
  int i, j;
  int ret = -1;
  for(j=0; s2[j] != '\0'; j++)
    for(i=0; s1[i] != '\0'; i++)
      if(s1[i] == s2[j])
        if(ret<0)
          ret = i;
        else if(i<ret)
          ret = i;
  return ret;
}

Solution by codybartfast

enum bool { NO, YES };

int any(char s1[], char s2[])
{
	int i, j;

	for (i = j = 0; s1[i] != '\0'; i++)
		if(contains(s2, s1[i]))
			return i;
	return -1;
}

int contains(char str[], char c)
{
	int i = 0;
	
	while (str[i] != '\0')
		if (c == str[i++])
			return YES;
	return NO;
}

Solution by Miguel Degrossoli

/* Exercise 2-5. Write the function "any(s1, s2)", which returns the first
 * location in a string "s1" where any character from the string "s2" occurs, or
 * "-1" if "s1" contains no characters from s2. (The standard library function
 * "strpbrk" does the same job, but returns a pointer to the location.) */

#include <stdlib.h>
#include <stdio.h>

#define MAXLEN	40	/* maximum size of the strings */
#define YES	 1
#define NO	 0

void mygetline(char s[], int lim);
int any(char s1[], char s2[]);

int main() {

	int c, i, lim;
	char s1[MAXLEN + 1], s2[MAXLEN + 1];

	lim = MAXLEN;

	printf("Enter s1: ");
	mygetline(s1, lim);

	printf("Enter s2: ");
	mygetline(s2, lim);

	c = any(s1, s2);

	if (c >= 0)
		printf("First match is \"%c\" in position %d of s1.\n",
				s1[c], c);
	else
		printf("No match found!\n");

	exit(0);
}

void mygetline(char s[], int lim) {

	int c, i;

	for (i = 0; i < lim && (c = getchar()) != '\n' && c != EOF; ++i)
		s[i] = c;

	s[i] = '\0';
}

int any(char s1[], char s2[]) {

	int i, j, n, found;

	for (i = j = 0; s1[i] != '\0'; ++i)
		for (n = 0; s2[n] != '\0'; ++n)
			if (s1[i] == s2[n])
				return i;

	return -1;
}

Produces result: 

miguel@Miguel-Notebook:~/Desenvolvimento/C$ ./exercise_2-5
Enter s1: Nice code!
Enter s2: Crap.
No match found!
miguel@Miguel-Notebook:~/Desenvolvimento/C$ ./exercise_2-5
Enter s1: Miguel Fernando Degrossoli
Enter s2: aeiou
First match is "i" in position 1 of s1.
 

Solution by anonymous (Category 0)

Simple, efficient, and compact. 

#include <stdio.h>

/*
Exercise 2-5. Write the function any(s1, s2), which returns the first location in the string s1 where any character from the string s2 occurs,
or -1 if s1 contains no characters from s2. (The standard library function strpbrk does the same job but returns a pointer to the location.)
*/

int any(char s1[], char s2[]);

int main()
{
    char str[] = "The quick brown fox jumped over the lazy dog!";
    printf("%s '%s' %d\n", str, " ", any(str, " "));
    printf("%s '%s' %d\n", str, "aeiouy", any(str, "aeiouy"));
    printf("%s '%s' %d\n", str, "bcdfghjklmn", any(str, "bcdfghjklmn"));
    printf("%s '%s' %d\n", str, "ABCDEFGHIJKLMNOPQRSTUVWXYZ", any(str, "ABCDEFGHIJKLMNOPQRSTUVWXYZ"));
    printf("%s '%s' %d\n", str, "!", any(str, "!"));
    printf("%s '%s' %d\n", str, "ABCDEFGHIJKLMNOPQRSUVWXYZ", any(str, "ABCDEFGHIJKLMNOPQRSUVWXYZ"));
    printf("%s '%s' %d\n", str, "\t", any(str, "\t"));
    return 0;
}

// squeeze: returns first location of any char within s2 that is found in s1. Returns -1 if no chars found
int any(char s1[], char s2[])
{
    int i, j;
    for (i = 0; s1[i] != '\0'; i++)
        for (j = 0; s2[j] != '\0'; j++)
            if (s1[i] == s2[j])
                return i + 1;
    
    return -1;
}
Retrieved from "https://clc-wiki.net/mediawiki/index.php?title=K%26R2_solutions:Chapter_2:Exercise_5&oldid=8488"
Personal tools