2
\$\begingroup\$

The following code implements the Boyer Moore string matching algorithm. The algorithm is used to find a sub-string (called the pattern) in a string (called the text) and return the index of the beginning of the pattern.

Looking for comments on correctness, efficiency, clarity and idiomatic C# usages. It passes all tests on LeetCode.

public static class BoyerMoore
{
    private static void Main(string[] args)
    {
        string text = "Hello World"
        string pattern = "World";
        Console.WriteLine(string.Join(",", IndexOf(text, pattern)));
    }

    public static IEnumerable<int> IndexOf(string text, string pattern)
    {
        if (pattern.Equals(""))
        {
            yield return 0;
            yield break;
        }

        // For an initial read of the algorithm, it is advisable to read this later, just assume you have a magic shift table computed
        int[] goodSuffixShifts = BuildGoodSuffixShifts(pattern);

        Dictionary<char, int[]> badCharacterShifts = BuildBadCharacterShifts(pattern);

        int i = 0;
        int goodSuffixCheck = -1;
        int goodSuffixSkip = 0;
        while (i + pattern.Length <= text.Length)
        {
            // Consider the pattern is placed so that its first character it under the ith character of the text
            // We started the matching from the right of the pattern
            int patternIndex = pattern.Length - 1;
            int textIndex = i + patternIndex;

            while (patternIndex >= 0 && text[textIndex] == pattern[patternIndex])
            {
                textIndex--;
                patternIndex--;

                // Here is an optimization for the good suffix case
                // If the shift is caused by a good suffix, we first count down the 
                // number of characters shifted, as we knew nothing about the text for 
                // those shifts
                if (goodSuffixCheck > 0)
                {
                    goodSuffixCheck--;
                }

                // Once we reach the point where we hit the known match
                if (goodSuffixCheck == 0)
                {
                    // Then we just skip all the known matches 
                    goodSuffixCheck = -1;
                    textIndex -= goodSuffixSkip;
                    patternIndex -= goodSuffixSkip;
                }
            }

            // If the loop ended with patternIndex == -1
            if (patternIndex == -1)
            {
                // The whole pattern matched
                yield return i;
            }

            // Figure out how many characters we can shift the pattern
            int matched = pattern.Length - patternIndex - 1;
            Debug.Assert(matched <= pattern.Length);

            int badCharacterShift = 0;
            if (patternIndex != -1)
            {
                // In case we have a mismatching character
                char badCharacter = text[textIndex];
                if (badCharacterShifts.ContainsKey(badCharacter))
                {
                    // In case the bad character does exist in the pattern
                    // We find the right most occurence of it and align them
                    badCharacterShift = badCharacterShifts[badCharacter][patternIndex];
                }
                else
                {
                    // Otherwise, the bad character is not seen, we can shift the pattern 
                    // so that it is after the bad character
                    badCharacterShift = patternIndex + 1;
                }
            }

            int goodSuffixShift = 0;

            if (goodSuffixShifts[matched] == 0)
            {
                // Ideally we would like to start compare the with the pattern shifted by the pattern length, for example, we can have:
                //
                // text                 : abceabcd
                // pattern before shift : abcd
                // pattern after shift  :     abcd
                //
                goodSuffixShift = pattern.Length;
            }
            else
            {
                // But it isn't always possible, in case a suffix of the pattern repeats within itself, for example, we can have:
                //
                // text                 : aaaaaaapqbbbbbbbbbbbb
                // pattern before shift : pqaxpqxpq
                // pattern after shift  :        pqaxpqxpq
                //
                // In the case above, we have determined that we have 2 matching characters, how do we determine that we should shift by 7 characters?
                // The key idea is that we know not just we have 2 matching character, we also know the third character doesn't match, 
                // this leads us to the notion of maximal suffix.
                //
                // A substring of the pattern is a maximal suffix if it matches a proper suffix of the pattern and either it can't extend the the left or
                // if it extended to the left, it is no longer matches a suffix pattern.
                //
                // In the example above, we have two maximal suffixes:
                // **
                //    ***
                // pqaxpqxpq
                // 
                // After the first match, we know 2 characters matches, therefore we would shift the pattern trying to align the length 2 maximal suffix
                // to the matched characters, we get the 7 characters shift as expected.
                //
                // The key question would be, why is it correct?
                // If we had a length 1 maximal suffix, aligning that one is not going to work, as we will fail at the second character.
                // If we had a length 3 maximal suffix, aligning that one is not going to work either, as we will fail at the third character, 
                // as we knew the third character of the text doesn't match with the pattern, but the length 3 maximal suffix does
                //
                // There is just one last twist, if we had more than one length 2 maximal suffix, we need to align it to the rightmost one to make sure
                // we don't skip potential hits
                //
                // Now go read the ComputeShiftTable() to see how the maximal suffixes are found and the shift table constructed
                //
                goodSuffixShift = goodSuffixShifts[matched];
            }

            if (badCharacterShift > goodSuffixShift)
            {
                // In case we have a bad character shift, we know nothing about what will match
                // after the shift (except, of course, the only character we are aligning to)
                // so we switch the goodSuffixCheck off
                goodSuffixCheck = -1;
                goodSuffixSkip = 0;
                i += badCharacterShift;
            }
            else
            {
                // In case we have a good suffix shift, we know the shifted characters are unknown
                // so they must be checked
                goodSuffixCheck = goodSuffixShift;

                // After going through the shifted characters, we know we reach a point where the string 
                // aligns
                if (matched == pattern.Length)
                {
                    // In case the whole pattern is matched, we know the full prefix matches
                    goodSuffixSkip = matched - goodSuffixShift;
                }
                else
                {
                    // Otherwise, we know the number of matched character in the suffix
                    goodSuffixSkip = matched;
                }
                i += goodSuffixShift;
            }
        }
    }

    private static Dictionary<char, int[]> BuildBadCharacterShifts(string pattern)
    {
        Dictionary<char, int[]> badCharacterShifts = new Dictionary<char, int[]>();
        for (int i = 0; i < pattern.Length; i++)
        {
            char c = pattern[i];
            int[] shift;
            if (!badCharacterShifts.TryGetValue(c, out shift))
            {
                // A new array is by default zero filled
                shift = new int[pattern.Length];
                badCharacterShifts.Add(c, shift);
            }

            // Therefore, we have a 1 in the array at the corresponding index if the 
            // character appears, and 0 otherwise
            shift[i] = 1;
        }

        foreach (int[] shift in badCharacterShifts.Values)
        {
            // A placeholder value to indicate the array is never shifted
            int lastShift = -1;
            for (int i = 0; i < shift.Length; i++)
            {
                if (shift[i] == 0)
                {
                    // At this point we are at a mismatch
                    if (lastShift == -1)
                    {
                        // There is no occurrence of the character before this position
                        // Therefore we can safely shift the pattern past the character
                        shift[i] = i + 1;
                    }
                    else
                    {
                        // Last time we shifted lastShift characters and then it aligns
                        // Therefore we can shift one more character now to align
                        shift[i] = ++lastShift;
                    }
                }
                else
                {
                    // Here we have as hit, the driver should not access this value
                    shift[i] = -1;
                    // And we need to shift no character to achieve alignment now
                    lastShift = 0;
                }
            }
        }

        return badCharacterShifts;
    }

    private static int[] BuildGoodSuffixShifts(string s)
    {
        int length = s.Length;
        int[] maximalSuffixLengths = new int[length - 1];
        int left = -1;
        int right = 0;
        for (int i = s.Length - 2; i >= 0; i--)
        {
            int currentLeft = i;
            int currentRight = i + 1;
            int prefixLeft = length - 1;
            if (left != -1)
            {
                // Here we have a maximal suffix, as always, we have:
                // s[left, right) = s[left + length - right, length)
                Debug.Assert(IsMaximalSuffix(s, left, right));

                if (left <= i && i < right)
                {
                    // Now we know s[i] lies inside the leftmost maximal suffix
                    // In particular, s[left, i + 1) = s[left + length - right, i + length - right + 1)

                    // So we are interested to see the maximal suffix starting from i + length - right
                    int knownRight = i + length - right + 1;

                    //   knownRight - 1 - i 
                    // = i + length - right + 1 - 1 - i
                    // = length - right > 0
                    // Therefore we know knownRight - 1 > i - we are always accessing the array that must have been already populated
                    Debug.Assert(knownRight - 1 > i);
                    int knownLength = maximalSuffixLengths[knownRight - 1];

                    int knownLeft = knownRight - knownLength;
                    Debug.Assert(knownLeft >= 0);

                    // In terms of the variables, we have
                    // s[knownLeft, knownRight) = s[knownLeft + length - knownRight, length)
                    Debug.Assert(IsSuffix(s, knownLeft, knownRight));

                    // We wish to use the relation s[left, i + 1) = s[left + length - right, i + length - right + 1)
                    // So we need to make sure s[knownLeft, knownRight) is substring of s[left + length - right, i + length - right + 1)
                    if (knownLeft < left + length - right)
                    {
                        knownLeft = left + length - right;
                    }
                    Debug.Assert(left + length - right <= knownLeft && knownLeft < length);
                    Debug.Assert(left + length - right < knownRight && knownRight <= length);

                    // Now we can shift them back, and this now we have this
                    // s[knownLeft, knownRight = i + 1) = s[knownLeft + length - knownRight, length)
                    knownLeft = knownLeft + right - length;
                    knownRight = knownRight + right - length;
                    Debug.Assert(knownRight == i + 1);
                    Debug.Assert(IsSuffix(s, knownLeft, knownRight));

                    currentLeft = knownLeft - 1;
                    prefixLeft = knownLeft + length - knownRight - 1;
                }
            }

            // Now, we extend the maximal suffix until we cannot

            // Note that in this loop, we are either exploring characters already discovered in a known maximal suffix
            // in which the loop should terminate right away because the maximal suffix terminated inside, or we are 
            // discovering new characters. Therefore the total time spent on this loop should be proportional to the length of s
            while (currentLeft >= 0 && s[currentLeft] == s[prefixLeft])
            {
                currentLeft--;
                prefixLeft--;
            }

            // We moved too much, adjust back
            currentLeft++;
            prefixLeft++;

            // Now we have found the maximal suffix
            Debug.Assert(IsMaximalSuffix(s, currentLeft, currentRight));

            // Book keeping for the left most maximal suffix
            if (left == -1 || currentLeft < left)
            {
                left = currentLeft;
                right = currentRight;
            }

            // And save the lengths
            maximalSuffixLengths[i] = currentRight - currentLeft;
        }

        // Make sure we have got it right in debug mode
        for (int i = 0; i < s.Length - 1; i++)
        {
            Debug.Assert(IsMaximalSuffix(s, i + 1 - maximalSuffixLengths[i], i + 1));
        }

        // Now we compute the shift table, the number of character matched could range from 0 to length
        int[] shifts = new int[length + 1];

        // Starting from the back
        for (int i = length - 2; i >= 0; i--)
        {
            int maximalSuffixLength = maximalSuffixLengths[i];

            // Note that i + shift = length - 1, this is designed so that the ith character aligns with the last character.
            int shift = length - 1 - i;

            if (shifts[maximalSuffixLength] == 0)
            {
                shifts[maximalSuffixLength] = shift;
            }
            if (shifts[length] == 0 && maximalSuffixLength == (i + 1))
            {
                //
                // In case the full pattern is matched, we will never have a maximal suffix with length n (it has to be proper)
                // Therefore the rule above cannot handle that special case, and must be analyzed differently
                //
                // Suppose a full pattern is matched:
                // text    : abcabcxxxxxxx
                // pattern : abcabc
                // 
                // In this case we know we should shift by 3, because the prefix matches a suffix. We can see that for any 
                // shift less than the pattern length, that has to be the case.
                // 
                // We can detect the prefix matches a suffix case by checking the maximal suffix starts at 0. Note that
                // when a maximal suffix starts at 0 and ends at i, it has length (i + 1), that is what the condition is checking
                // 
                // Again, if we have multiple ways such that prefix matches suffix, we pick the one with least shift to make sure 
                // we capture all occurences, this could happen in this case:
                //
                // text    : aaxaaxaa
                // pattern : aaxaa
                //
                // In this case we can only shift by 3, not 4.
                //
                shifts[length] = shift;
            }
        }

        return shifts;
    }

    private static string SubstringLeftRight(this string s, int left, int right)
    {
        if (left == s.Length)
        {
            Debug.Assert(right == s.Length);
            return "";
        }
        else
        {
            Debug.Assert(left >= 0);
            Debug.Assert(right >= 0);
            Debug.Assert(right <= s.Length);
            Debug.Assert(right >= left);
            return s.Substring(left, right - left);
        }
    }

    private static bool IsSuffix(string s, int left, int right)
    {
        return s.SubstringLeftRight(left, right) == s.SubstringLeftRight(left + s.Length - right, s.Length);
    }

    private static bool IsMaximalSuffix(string s, int left, int right)
    {
        if (IsSuffix(s, left, right))
        {
            if (left > 0)
            {
                return !IsSuffix(s, left - 1, right);
            }
            else
            {
                return true;
            }
        }
        return false;
    }
}
| improve this question | | | | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Please add the description of the task to your question. \$\endgroup\$ – t3chb0t Dec 28 '18 at 18:46
3
\$\begingroup\$

Bugs

  • IndexOf("BC.xABC..ABC", "BC..ABC") does not find a match, because your good-suffix table logic does not calculate shifts for situations where a suffix of the match is a prefix of pattern.
  • IndexOf("x.ABC..ABC", "..ABC") fails with an IndexOutOfRangeException. This is because you always apply the good-suffix skip logic (the Galil rule) after a good-suffix shift, even when the suffix did not occur elsewhere in the pattern.

IndexOf

  • Returning 0 if pattern is an empty string leads to inconsistent results: IndexOf(text.Substring(1), "") returns 0, so you'd expect the result of IndexOf(text, "") to include 1, but that's not the case. I would throw an exception instead.
  • IndexOf is public, but it doesn't check whether it's arguments are valid. I'd expect an ArgumentNullException if either text or pattern is null.
  • I would rename this method to IndexesOf. It's more accurate, and it allows you to make it an extension method without name-clashes.
  • The if (goodSuffixCheck == 0) check is only useful if the previous check succeeded, so this should be moved into the above if body. This happens inside a loop after all.
  • The name matched sounds like a boolean - matchLength is a more descriptive name.
  • In the bad-character shift lookup, use TryGetValue instead of ContainsKey, so you only need a single lookup.
  • The comment // In case the bad character does exist in the pattern // We find the right most occurence of it and align them is not correct - you don't want the right-most occurrence, but the first occurrence to the left of the current position.
  • if (goodSuffixShifts[matchLength] == 0) { goodSuffixShift = pattern.Length; } - why not store the pattern length in this shift table during pre-processing?
  • While it's useful to see a description of a complicated algorithm, inserting such large comments in-between the code makes it more difficult to get an overview of the code itself, because it's so fragmented. I would prefer fewer and much more succinct in-line comments, and - if necessary - a more extensive explanation elsewhere (such as at the top of the file).

BuildBadCharacterShifts

  • You can shorten Dictionary<char, int[]> badCharacterShifts = new Dictionary<char, int[]>(); to var badCharacterShifts = new Dictionary<char, int[]>();.
  • out parameters can be declared in-line: if (!badCharacterShifts.TryGetValue(c, out int[] shift)).
  • Comments like // A new array is by default zero filled are clutter, in my opinion. There are plenty of places to read up on C# if someone is not sufficiently familiar with the language. I guess it depends on the target audience though.
  • Why not mark occurrences with -1? That saves a tiny bit of work further down. You may want to add an assertion in IndexOf to make sure that a -1 shift is never used, just in case.
  • The foreach loop can be simplified - the lastShift == -1 edge-case can be taken care of by the general shift[i] = ++lastShift case, if you initialize lastShift to 0.

BuildGoodSuffixShifts

  • I'd rename s to pattern, for consistency's sake.
  • Using both length and s.Length is inconsistent. Personally I'd stick to s.Length, so it's more obvious what length you're working with.
  • This method is fairly long. A helper method for finding a maximal suffix for a certain end position would be useful - not only to make this method shorter, but properly named helper methods can also make the intention of the code more clear. This is actually a good place for a local function.
  • Many comments here look very similar to the code, with a lot of left + length - right and similar expressions. That's like saying that Frob(widget) frobs the widget, without explaining what frobbing is or why the widget needs to be frobbed. It doesn't really make the code easier to understand.
  • The if (left != -1) part is actually an optimization, but that's not clearly explained. When inside an already known maximal suffix, it's sometimes possible to skip a few comparisons, but neither the code nor the comments make that very clear (expressions like i + length - right + 1 aren't as easy to understand as I'd like).
  • Picking better initial values sometimes lets you simplify code. For example, initializing left to s.Length removes the need for that left != -1 check.

Other methods

  • There's no need for that if/else check in SubstringLeftRight - the else body already takes care of the empty-string edge-case.
  • I'd rename left and right to startIndex and endIndex, to be more consistent with string.Substring's parameter names.
  • The right >= 0 assert in SubstringLeftRight's else body is superfluous.
  • IsSuffix can be simplified by using string.EndsWith. And with that, there's very little need left for SubstringLeftRight.

Other notes

  • I would add messages to those Debug.Assert calls, so you can immediately see which assertion failed.
  • If you plan to use this code, then you may want to create a SearchPattern class that can store the shift tables for a pattern, so searching multiple texts with the same pattern will be faster because you don't need to repeat the pre-processing each time.
  • Using LeetCode as a 'unit test repository' is a smart idea, but note that you're returning the index of all matches, while their tests are geared towards finding only the first match. That might explain why those tests didn't catch the above two bugs. What I did was a basic form of fuzz-testing: generate a few random patterns, randomly join them together (a few hundred times for the text, a few times for the pattern) and feed that into the algorithm, then repeat that a few thousand times. The next step would've been writing a simple verification method (using repeated string.IndexOf calls), but at that point I had already found 2 bugs so I decided that was enough.
| improve this answer | | | | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.