2

I found code:

char *BoyerMoore_negative(char *string, int strLength)
{
    char *data ="nice bad good worst";
    int dataLength = strlen(data) - 1;
    int skipTable[256], i;
    char *search;
    register char lastChar;

    if (strLength == 0)
        return NULL;

    // Initialize skip lookup table
    for (i = 0; i < 256; i++)
        skipTable[i] = strLength;   //strlength is numbers of words in sentence

    search = string; //string is array of words in the sentence
    i = --strLength; // Decrease strLength here to make it an index

    do {
        skipTable[*search++] = i; // ---> skiptable is int array and search is string. Then what happens on LHS on each iteration???
    } while (i--);

    lastChar = *--search; // ---> Decreamenting string pointer? What does it mean on RHS?

    do {
        // Have we found the entire string?
        if (i-- == 0)
            return search;
    } while (*--search == string[i]);

    // Skip past the part of the string that we scanned already
    search += (strLength - i + 1);     ---> what happends here?
    dataLength--;

Can someone give hint of ---> pointers? I dont know whether I can ask this kinda question or not but for my understanding these concept I did!

Improve this question
16
  • 5
    Don't use char * to point to a string literal, use const char *, or, better, std::string. Commented Aug 15, 2013 at 9:36
  • 5
    You need a good book or tutorial. See e.g. the lists here. Commented Aug 15, 2013 at 9:36
  • 1
    @Karimkhan, String literals are not modifiable. If you try to do so, the const is the difference between a compiler error and UB. In C++11, you're not even allowed to have a char * pointing to a string literal. Commented Aug 15, 2013 at 9:38
  • 4
    @Karimkhan I might refuse to work with you if you wrote this in a c++ program I had to work on... Commented Aug 15, 2013 at 10:01
  • 2
    @Karimkhan the rule of thumb here is: If you use C, use C. If you use C++, use C++. But don't use C and give it as C++. Commented Aug 15, 2013 at 10:12

2 Answers 2

Reset to default
1 
skipTable[*search++] = i;

This is actually hazardous on a platform where char may be signed, in which case some values could produce a negative index and an illegal access. Should be:

skipTable[*search++ & 255] = i;

What it and its surrounding loop do is to populate skipTable with some information about each character you might discover in your search space. Specifically, if you find character c as you search, then the value of skipTable[c] will be how far from the start of the string you're searching for that that character appears. If it does not appear in that string then we get the default maximum value -- the length of the whole string.

lastChar = *--search;

This means that the value of search before the expression is pointing one character further on than we wanted it to. That is, it counted right off the end of the string and is now pointing at (probably) a NUL character. We want to subtract one from that, and then see what character it's pointing to. We also want to keep the modified value of search.

search += (strLength - i + 1);

You seem to have deleted some code for brevity, so it's hard to say exactly what's going on, here.

What it looks like is that it's just performed a string comparison, starting at the far end of the strings, and found a mismatch. i probably counted down from strLength while string decremented from the end of the string to be compared. In that case, the line above would re-set search to where it pointed before the start of the comparison, plus one more character to begin the search from that point.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thank a lot, yes it compares string char by char!
1

I presume you know what the code is supposed to do. The function has a very evocative name.

So, addressing the queries in code directly, without analysing the code too much (it's incomplete):

search is a pointer. Not the string itself, but a pointer to that string. One might expect string to be pointing the start of some string, and search is set to point to the same value.

skipTable[*search++] = i; dereferences the pointer, obtaining the value at whatever search was pointing at, and then increments the pointer. Since skipTable is an array of 255 ints and search is a char pointer, this will never fall out of bounds on x86 if a char is unsigned (compiler dependent). Really, there should be a cast; skipTable[(unsigned char) *search++]. (strictly speaking, this still isn't portable).

So i is set to the value at skipTable[*search] and search (which is a pointer) is incremented (presumably to point to the next value in some array).

lastChar = *--search; is similar to before. search is decremented and then dereferenced. So this gets the previous value in the string.

search += (strLength - i + 1); again, a pointer is being increased. If strLength represents the length of a string

As has been pointed in out in comments, the following is not a good idea: char *data ="nice bad good worst"; The string you've defined in code cannot be modified, but because you have a pointer to it, you're allowed to try. The result of trying to modify the string pointed to be data is undefined, but will almost invariably result in a crash.

Improve this answer

2 Comments

"Since skipTable is an array of 255 ints and search is a char pointer, this will never fall out of bounds on x86." Except that char could be signed. And quite likely is.
That is true. There should be a cast as well.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.