Implementation of strspn( )

Question

The definition of library function strspn is:

size_t strspn(const char *str, const char *chars)

/* Return number of leading characters at the beginning of the string `str`
   which are all members of string `chars`. */

e.g. if str is "fecxdy" and chars is "abcdef" then the function would return 3, since f, e and c all appear somewhere in chars, giving 3 leading characters of str, and x is the first character of str which is not a member of chars.

Could someone help me write an implementation of strspn in C. The only library function I am allowed to call from the implementation is strlen?

Answer 1

Create a lookup table (a poor man's set) for all possible ASCII chars, and just lookup each character in str. This is worst case O(max(N,M)), where N is the number of characters in str and M is the number of characters in chars.

#include <string.h>

size_t strspn(const char *str, const char *chars) {
  int i;
  char ch[256] = {0};

  for (i = 0; i < strlen(chars); i++) {
    ch[chars[i]] = 1;
  }

  for (i = 0; i < strlen(str); i++) {
    if (ch[str[i]] == 0) {
      break;
    }
  }

  return i;
}

This could also be solved without using strlen at all, assuming both strings are zero-terminated. The disadvantage of this solution is that one needs 256 bytes of memory for the lookup table.

Answer 2

int my_strspn(const char *str1,const char *str2){
int i,k,counter=0;
for(i=0;str1[i]!='\0';i++){
 if(counter != i) break;
 for(k=0;str2[k]!='\0';k++){
  if(str1[i]==str2[k])
   counter++;
 }
}
 return counter;
}

Answer 3

A naive implementation of strspn() would iterate on the first string, as long as it finds the corresponding character in the second string:

#include <string.h>
size_t strspn(const char *str, const char *chars) {
    size_t i = 0;
    while (str[i] && strchr(chars, str[i]))
        i++;
    return i;
}

Given that you are not allowed to call strchr(), here is a naive native implementation:

size_t strspn(const char *str, const char *chars) {
    size_t i, j;
    for (i = 0; str[i] != '\0'; i++) {
        for (j = 0; chars[j] != str[i]; j++) {
            if (chars[j] == '\0')
                return i; // char not found, return index so far
        }
    }
    return i;  // complete string matches, return length
}

Scanning the second string repeatedly can be costly. Here is an alternative that combines different methods depending on the length of chars, assuming 8-bit bytes:

size_t strspn(const char *str, const char *chars) {
    size_t i = 0;
    char c = chars[0];

    if (c != '\0') {  // if second string is empty, return 0
        if (chars[1] == '\0') {
            // second string has single char, use a simple loop
            while (str[i] == c)
                i++;
        } else {
            // second string has more characters, construct a bitmap
            unsigned char x, bits[256 / 8] = { 0 };
            for (i = 0; (x = chars[i]) != '\0'; i++)
                bits[x >> 3] |= 1 << (x & 7);
            // iterate while characters are found in the bitmap
            for (i = 0; (x = str[i]), (bits[x >> 3] & (1 << (x & 7))); i++)
                continue;
        }
    }
    return i;
}

Answer 4

I think this should be pretty fast

size_t strspn(const unsigned char *str, const unsigned char *chars){
    unsigned char ta[32]={0};
    size_t i;
    for(i=0;chars[i];++i)
        ta[chars[i]>>3]|=0x1<<(chars[i]%8);
    for(i=0;((ta[str[i]>>3]>>(str[i]%8))&0x1);++i);
    return i;
}

Thanks to others for sanity checks.

Answer 5

Well, implementing a standard library for my OS, here is my solution (C++).

KCSTDLIB_API_FUNC(size_t DECL_CALL strspn(const char * str1, const char * str2))
{
size_t count = 0;
auto isin = [&](char c)
{
    for (size_t x = 0; str2[x]; x++)
    {
        if (c == str2[x])
            return true;
    };
    return false;
};
for (; isin(str1[count]); count++);
return count;
}

Answer 6

I found this question while going over old exams. You weren't allowed to use indexing or any standard functions. Here's my attempt at a solution:

#include <stdio.h>    
size_t myStrspn(const char *str1, const char *str2){
  size_t i,j;
  i=0;

  while(*(str1+i)){
    j=0;
    while(*(str2+j)){
      if(*(str1+i) == *(str2+j)){
        break; //Found a match.
      }
      j++;
    }
    if(!*(str2+j)){
      return i; //No match found.
    }
    i++;
  }
  return i;
}

void main(){
  char s[] = "7803 Elm St.";
  int n = 0;
  n = myStrspn(s,"1234567890");
  printf("The number length is %d. \n",n);
}

Here's the solution from the exam:

#include<stdio.h>
size_t strspn(const char* cs, const char* ct) {
  size_t n;
  const char* p;
  for(n=0; *cs; cs++, n++) {
    for(p=ct; *p && *p != *cs; p++)
      ;
    if (!*p)
      break;
  }
  return n;
}

For loops made it much more compact.

Answer 7

Without touching a C-compiler for the last couple of years. From the top of my head something like this should work:

int spn = 0;
while(*str++ != '\0')
{
  char *hay = chars;
  bool match = false;
  while(*hay++ != '\0')
  {
     if(*hay == *str)
     {
       match = true;
       break;
     }
  }

  if(match)
     spn++;
  else
     return spn;
}
return spn;

Answer 8

The basic idea is to step through the string, one character at a time, and test if it's in the character set. If it's not, stop and return the answer. In pseudocode, that would look like:

count = 0
for each character c in str
    if c is not in chars
        break
    count++
return count

The if c is not in chars test can be implemented by iterating through all of the characters of chars and testing if c matches any of the characters. Note that this is not the fastest implementation, since it involves stepping through the chars string for each character in str. A faster implementation would use a lookup table to test if c is not in chars.