Find char sequence inside char array.

[PacR]

Hello i am trying to make a program witch will find a sequence of chars inside char array, but my program don't work correctly need help.
Here is my code:

#include <iostream>

int main()
{
    char MyCharArray[] = "mna89ybchellomas09as9";
    char Key[] = "hello";

    unsigned int KeyNumb = 0;
    unsigned int CorrectInRow = 0;

    for(unsigned int i = 0; i < sizeof(MyCharArray); i++){
        if(MyCharArray[i] == Key[KeyNumb]){ // Check if char inside MyCharArray match with first char inside Key.
            CorrectInRow++; // Increment this because i want to know how many chars match in a row.
            KeyNumb++; // Increment this because now i know that next time in this loop i will want to check the next char inside Key[].
            if(CorrectInRow == sizeof(Key)){ // if CorrectInRow match sizeof(Key) then i know that i have a match inside MyCharArray.
                std::cout << "Found: " << Key << " At: " << i << std::endl; // Print out where and what i found.
                break; // Close the for loop.
            }
        }
        else{
            KeyNumb = 0; // Setting this to zero because if MyCharArray[i] did not match Key[KeyNumb] and next time i want to check the first char inside Key[].
            CorrectInRow = 0; // Setting this to zero because MyCharArray[i] did not match Key[KeyNumb].
        }
    }
    return 0;
}

Thank you for reading.

[salem c]

> char Key[] = "hello";
...
> if(CorrectInRow == sizeof(Key))
strlen(Key) == 5
sizeof(Key) == 6

sizeof() will count the \0 at the end of the string, but you never match a \0 unless you happen to be at the end of MyCharArray as well.

[PacR]

Thank you salem c.

[dutch]

As salem said, CorrectInRow will never equal sizeof(Key) (unless the match occurs at the end of the string). Recall that sizeof(Key) is the actual size of the character array, not the length of the string as given by strlen. The length of the character array includes the terminating '\0' character (and any chars in the array beyond that, although the way you've initialized the arrays precludes that). So you need to compare to sizeof(Key) - 1.

Actually, you don't need to use sizeof or strlen at all since you can use the '\0' character to tell when you've reached the end of the string.

Also note that you don't need both CorrectInRow and KeyNumb since they always have exactly the same value.

And the substring code should be written as a function that's called from main.

[MikeStgt]

Is this the Knuth–Morris–Pratt algorithm?

[PacR]

MikeStgt i don't know what kind of algorithm it is. I just make this up.

[MikeStgt]

Find a description KMP Pattern Matching in English language here:
https://www.youtube.com/watch?v=GTJr8OvyEVQ
with English subtitles. So everybody has a true chance to grasp it.

[jonnin]

for c-strings, to find substring is strstr(this, in_that);
you can treat this result as a boolean if you only want to know if its in there.

eg
char MyCharArray[] = "mna89ybchellomas09as9";
char Key[] = "hello";
if( strstr(key,MyCharArray) )
cout << "found" ;
else
cout << "not found";

this is not pattern matching, its just a dumb comparison and case matters.

you will need to understand pointers pretty well to proceed. to check key without the first letter, then...
for(i = 0; i < strlen(key); i++)
... strstr(&key[i],MyCharArray) etc

and to get at the data, you have to check against null first and then use the pointer that comes from strstr...
because you want the LOCATION not a pointer to it, find() and std::string would be far better for this code than c-strings. Getting the location etc is going to take pointer math in C.

[MikeStgt]

you will need to understand pointers pretty well to proceed.

Still a beginner I do not understand too much about C++. Frankly, I am able to code some simple procedures, but no concepts with classes and threads. And to be honest, the following example are two C functions I found somewhere, I only added int main(). As side effect I learned that a string is (according the reference) convertible to several other types excluded char.

I added to the KMP function an optional argument, it allows to start the search not at the beginning of the text (default). This allows to find all occurrences of the search string, one by one.

/* Knuth-Morris-Pratt algorithm */
#include <iostream>     // cout
// #include <string>       // string
#include <cstring>      // strlen
using namespace std;


void preKmp(char *x, int m, int kmpNext[])
{
   int i, j;

   i = 0;
   j = kmpNext[0] = -1;
   while (i < m)
   {
      while (j > -1 && x[i] != x[j])
         j = kmpNext[j];
      i++;
      j++;
      if (x[i] == x[j])
         kmpNext[i] = kmpNext[j];
      else
         kmpNext[i] = j;
   }
}


int KMP(char *x, int m, char *y, int n, int start=0)
{
   int i(0), j(start), kmpNext[m];

   /* Preprocessing */
   preKmp(x, m, kmpNext);

   /* Searching */
   while (j < n)
   {
      while (i > -1 && x[i] != y[j])
         i = kmpNext[i];
      i++;
      j++;
      if (i >= m)
         return (j - i);
   }
   return (-1);
}

int main()
{
    char needle[] = "hello";
    char haystack[] = "hellas!--mna89ybchellomas09as9";

    cout << "Search string found in text at possition " << KMP(needle, strlen(needle), haystack, strlen(haystack)) << " (0-based, -1 = not found).";
}

I am not happy with this C/C++ mixture, it does not look 'nice'.

[jonnin]

int main()
{
string needle = "hello";
string haystack[] = "hellas!--mna89ybchellomas09as9";

cout << "Search string found in text at possition " << haystack.find(needle) << endl; //if not found, the result is string::npos which is 0xFFFFFF for whatever size t can hold
}

The OP is using c-strings though.
you need
char *cp = strstr(needle, haystack);
if(cp)
cout << "words" << cp-haystack; //I think this is the pointer math you need.
or syntax to make that compile (may need &haystack[0] or something)
else cout not found etc

the point is probably to study the Knuth algorithm, though …. not clear from the OP? If studying the algorithm, you do need to DIY.

I prefer strstr over find generally speaking. Could be I am old. Could be find is terrible. I can't make up my mind :P The reason is most of the time I just want to know if its there, and don't really care where.

[MikeStgt]

you do need to DIY

Really? IMO no, not at all. It is for the first time that I have a closer look to the Knuth-Morris-Pratt algorithm, up to now I only knew there is a faster way than hunting for a match "single step wise". Decades ago I asked in another forum, why the find stage is slower than the editor (XEDIT) when looking for a pattern. One of the answers mentioned KMP, or Morris-Pratt at least. So many years before I already used this algorithm without knowing it exists.

For me it's enough to know 'there is something' and to know where to find the details when needed. With this "sophisticated ignorance" I even do not know if the a. m. example program is Knuth-Morris-Pratt or just Morris-Pratt. For this detail I would go when I need it.