Using strtok to find substring

Question

I have a string of many letters

string path = "cxzaserds";

and a target word

string word = "cars";

In my function match(), I want to return true if the characters from word are found (in order) in path, in this case it would return true ('c' comes before 'a' comes before 'r' comes before 's' in the path string).

I'm trying to use strtok() to find each character one after another, with the delimiter being the current index's letter.

my progress:

bool match (string path, string word)
{
  char * cstr = new char [path.length()+1]; //workaround for strtok on string
  std::strcpy (cstr, path.c_str());

    char *p;

  for (int i = 0 ; i < path.length(); i++)
    {
    //error here, "invalid conversion from 'char' to 'const char*'
      p = strtok (cstr, word[i]);

      if (p != NULL) //if strtok found word[i]
        continue;
      else return false; //was NULL, word not found
    }

  return true; //made it through, return true
}

On the C++ page, under delimiters, it says:

These can be different from one call to another.

http://www.cplusplus.com/reference/cstring/strtok/

What can I do to change the delimiter as strtok returns non-null? Or another (easier) solution altogether?

2nd parameter for `strtok` is `char*`, not `char` and `word[i]` is `char`. It's a **list of delimiters**, not single one. What I'd do? Drop `strotk` in favor of something more C++ish. [Related post](http://stackoverflow.com/a/27250298/1207195). — Adriano Repetti, Apr 16 '15 at 07:09

Vlad from Moscow · Answer 1 · 2015-04-16T08:00:10.120

I already answered this question so I do not want to repeat it entirely here. This question was asked here but I can not find it. However you can see the answer at my personal forum

Though the answer is written in Russian nevertheless the code is written in English.:) And moreover you can translate the description using web service translate.

As for using standard C function strtok with objects of type std::string then it is simply a bad idea and shall not be used.

The other approach is to use standard algorithm std::all_of along with standard C function strchr

score 0 · Answer 2 · answered Apr 16 '15 at 07:45

0

You've written:

p = strtok(cstr, word[i]);

As second parameter, you are passing ith character (type of which is char).

However, as the documentation states, second argument must be of type const char *, which means it's an array of delimiters. So you have a type mismatch.

The simplest solution would be to create an array of delimiters (note it's NUL-terminated, to it's actually a C-style string with one letter only):

char delimiters[] = { word[i], '\0' };

And then use it like this:

p = strtok(cstr, delimiters);

On the other hand, this approach is non-C++ style, and probably in real life you'd want to something else.

answered Apr 16 '15 at 07:45

rubikonx9

1,403
15
27

Why the downvote? Perhaps it's not the best solution, but it's valid and solves the issue described. – rubikonx9 Apr 16 '15 at 07:47
Not my downvote, but you're overcomplicating the target problem using a function that's not really made for this purpose (since it does a lot more). – Mario Apr 16 '15 at 07:52
I agree. Anyway, it's not off-topic, and it might be a good opportunity for @filposs to learn more on C types, as it seems he has some difficulties with this. Do we have a saboteur here? Other (even more correct) answers got downvoted too. – rubikonx9 Apr 16 '15 at 07:59

6502 · Answer 3 · 2015-04-16T09:14:45.437

strchr is much better than strtok for this problem; actually as others mentioned strtok is really badly designed and it's hard to think cases in which it's a good idea to use it.

strchr looks for the first occurrence of a character in a C string.

This problem using strchr becomes a one-liner even in C:

int match(const char *needle, const char *haystack) {
    while (haystack && *needle) {
        haystack = strchr(haystack, *needle++);
    }
    return haystack != NULL;
}

score 0 · Accepted Answer · answered Apr 16 '15 at 07:47

As Vlad mentioned, you shouldn't mix STL code (std::string) and classic c code (strtok()).

Instead you can use std::string members like find() or find_first_of() to solve your issue:

bool match(const std::string &path, const std::string &word) {
    std::size_t pos = 0; // position of the last match

    // iterate over all characters in 'word'
    for (std::size_t i = 0; i < word.length(); ++i) {
        // look for the next character and store the new position
        if ((pos = path.find(word[i], pos)) == std::string::npos)
            return false; // return false if it couldn't be found
    }
    return true; // all characters have been found in order
}

score 0 · Answer 5 · answered Apr 16 '15 at 09:25

Given your problem and the fact that C/C++ will allow you to address individual characters with plain subscripting then strtok would only seem to complicate the solution.

Something like (untested code!):

boolean hasWord ( char * needle, char * haystack) {
   int nlen = strlen(needle);
   int npos = 0;
   int hlen = strlen(haystack);
   int hpos = 0;
   for (hpos = 0 ; hpos < hlen ; hpos++) {
        if (needle[npos] == haystack[hpos]) {
            // got a match now look for next letter
            npos++;
            if (npos >= nlen) {
                // all letters now matched in sequence
                return true;
            }
        }
   }
   return false;
}

Using strtok to find substring

5 Answers5