Unit 8: Pattern Matching - Subjective Questions

Pattern matching is the problem of locating occurrences of a shorter string, called the pattern, within a longer string, called the text.

• Let the text be of length .
• Let the pattern be of length , where .
• The objective is to find every valid shift such that:

The output is the set of starting indices at which the pattern occurs. Depending on the application, an algorithm may return the first occurrence, all occurrences, or report that no match exists.

Applications include:

• Searching words in text editors and search engines
• DNA and protein sequence analysis
• Plagiarism and document similarity detection
• Intrusion detection and log analysis
• Lexical analysis in compilers

The design of a pattern matching algorithm depends on several considerations:

• Input sizes: The text length is usually much larger than the pattern length .
• Preprocessing: Algorithms such as KMP and Boyer-Moore preprocess the pattern to avoid unnecessary comparisons.
• Repeated information: After a mismatch, previously matched characters should be used to determine a safe shift.
• Alphabet size: Boyer-Moore often performs better when the alphabet is large because larger shifts are possible.
• Number of searches: Pattern preprocessing is particularly useful when the same pattern is searched in multiple texts.
• Space usage: Auxiliary tables improve speed but consume additional memory.
• Required output: Finding all occurrences requires handling overlapping matches correctly.

A good algorithm minimizes repeated comparisons while ensuring that no valid occurrence is skipped.

The brute-force algorithm aligns the pattern at every possible position in the text. At each alignment, it compares corresponding characters from left to right.

Pseudocode:

BruteForceMatch(T, P):
    n = length(T)
    m = length(P)
    for s = 0 to n - m:
        j = 0
        while j < m and T[s + j] == P[j]:
            j = j + 1
        if j == m:
            report s

At shift , the algorithm checks whether equals . If a mismatch occurs, it shifts the pattern exactly one position to the right and starts again. The method requires no pattern preprocessing and uses auxiliary space.

The brute-force algorithm examines every possible alignment of a pattern of length in a text of length .

There are valid shifts:

For each shift , the algorithm compares every pair and until either a mismatch is found or all characters match.

• If all characters match, then by definition occurs in at shift , so reporting is correct.
• If a mismatch is found, the pattern cannot occur at that shift.
• Since every possible shift is examined, no valid occurrence can be omitted.

Therefore, the algorithm reports every occurrence and reports no invalid occurrence. Hence, the brute-force pattern matching algorithm is correct.

There are possible pattern alignments.

Best case: A mismatch occurs at the first character of every alignment. The number of comparisons is , giving:

Worst case: At each alignment, all characters are compared, or a mismatch occurs only at the last character. The number of comparisons is at most:

Therefore, the worst-case complexity is . This occurs, for example, when the text and pattern contain many repeated characters.

Space complexity: The algorithm stores only loop indices and therefore uses auxiliary space.

Although simple and memory-efficient, brute force can perform many redundant comparisons.

The text has length and the pattern has length . Therefore, shifts from through are examined.

• Shift 0: AABA matches AABA; report index .
• Shifts 1 to 8: Each alignment contains at least one mismatch.
• Shift 9: Text substring AABA matches the pattern; report index .
• Shift 10: A mismatch occurs.
• Shift 11: Text substring AABA matches the pattern; report index .
• Shift 12: A mismatch occurs.

Thus, the set of starting positions is:

The matches at indices and overlap. The example shows why an algorithm must continue searching after finding a match when all occurrences are required.

The LPS array stores the length of the longest proper prefix of each pattern prefix that is also its suffix.

For each index , is the greatest length such that:

A proper prefix cannot be the complete string itself. For example, for ABAB, the longest proper prefix that is also a suffix is AB, so its LPS value is .

The array is useful after a mismatch. If pattern characters have already matched, KMP sets to rather than moving back in the text. This preserves the longest prefix that is already known to match a suffix of the processed text and prevents redundant comparisons.

For the pattern AABAACAABAA, the LPS array is:

Hence:

During construction, maintain a candidate prefix length . If , increment and assign it to . On a mismatch with , replace by and retry. If , assign zero and advance. This computes the complete array in time.

The KMP algorithm preprocesses the pattern into an LPS array and uses it to avoid moving the text index backward after a mismatch.

Pseudocode:

KMP(T, P):
    LPS = BuildLPS(P)
    i = 0
    j = 0
    while i < length(T):
        if T[i] == P[j]:
            i = i + 1
            j = j + 1
            if j == length(P):
                report i - j
                j = LPS[j - 1]
        else if j > 0:
            j = LPS[j - 1]
        else:
            i = i + 1

Here, indexes the text and indexes the pattern. After a mismatch, KMP retains the longest pattern prefix that can still match the processed text suffix. After a complete match, using allows overlapping occurrences to be found.

Suppose the first pattern characters have matched and a mismatch occurs between and . Thus, the processed text ends with the matched string .

The LPS value identifies the longest proper prefix that is also a suffix of . Therefore, those suffix characters of the processed text already match the first pattern characters.

KMP sets and compares the same text character again. Any shift smaller than this would require a longer border than , contradicting the definition of LPS. Any discarded alignment has already been shown to be impossible by the mismatch or by the absence of a suitable border.

Thus, KMP skips only invalid alignments and cannot miss a valid occurrence.

KMP consists of two phases.

1. LPS preprocessing: The pattern index advances or the candidate prefix length falls to a smaller LPS value. The total work is .

2. Text search: The text index never moves backward. On a match it advances, and after a mismatch either advances or the pattern index decreases. The total number of such changes is linear, so searching takes time.

Therefore, the total time is:

The LPS table contains integers and requires auxiliary space. Other variables use constant space.

KMP provides a worst-case linear-time guarantee, unlike the worst case of brute-force matching.

For pattern ABABCABAB, the LPS array is:

The search proceeds as follows:

• The initial characters ABAB match at text index .
• The next comparison mismatches because the text has D while the pattern expects C.
• KMP uses the LPS value , then eventually falls back to , without moving the text index backward.
• The search continues through ABACD; partial matches are reused through the LPS table.
• Beginning at text index , all characters of ABABCABAB match.

The occurrence is therefore reported at:

The key feature is that KMP reuses border information after each mismatch instead of restarting every comparison from the next text position.

For pattern AAA, the LPS array is:

KMP first matches the pattern at text index . After reporting the match, it does not reset the pattern index to zero. Instead, it assigns:

Two characters are therefore retained as an already matched prefix. The next text character completes another occurrence at index . The same fallback finds a third occurrence at index .

Thus, the starting positions are:

Using the final LPS value after a match is essential for finding overlapping occurrences efficiently.

Boyer-Moore compares pattern characters with the text from right to left. When a mismatch occurs at pattern index , the bad character is the mismatching text character .

Let be the rightmost index of in the pattern, or if is absent. The bad-character shift is:

• If does not occur in the pattern, the pattern can move completely beyond that text character.
• If occurs to the left of , its rightmost occurrence is aligned with the bad character.
• If its rightmost occurrence lies to the right of , the minimum safe shift is one.

The table of rightmost occurrences can be built in time when explicitly initialized for alphabet , or in expected time using a map.

The pattern NEEDLE has indices:

The bad-character table stores the rightmost occurrence:

• for any other character

If a mismatch occurs at pattern index against text character D, then:

If the bad character is X, which is absent from the pattern, then:

Thus, characters absent from the pattern often permit large shifts.

The good-suffix heuristic applies when a suffix of the pattern has matched but a mismatch occurs immediately to its left.

Suppose has matched the text. Boyer-Moore shifts the pattern using one of these cases:

• Another occurrence exists: Align another occurrence of the matched suffix in the pattern with the same text substring, preferably one whose preceding character differs from the mismatched pattern character.
• A partial suffix exists: If the complete suffix does not reappear, align the longest suffix of the matched portion that is also a prefix of the pattern.
• No suitable substring exists: Shift the pattern completely beyond the matched suffix.

The required shifts are precomputed from the pattern. Combined with the bad-character heuristic, Boyer-Moore normally selects the larger safe shift, allowing it to skip many text positions.

Boyer-Moore preprocesses the pattern to create bad-character and good-suffix shift information. At each alignment, it compares characters from the pattern's right end toward its left end.

Procedure:

• Set the initial shift .
• Compare with and continue right to left while characters match.
• If every character matches, report and apply a safe match shift.
• On a mismatch, compute both heuristic shifts and move by the larger safe value.
• Repeat while .

Performance:

• Preprocessing requires time and space in a common table-based implementation.
• In practice, the search is often sublinear because not every text character is inspected.
• A basic bad-character-only version can degrade to .
• With the full heuristics and standard refinements, Boyer-Moore can achieve linear worst-case searching.

It is especially effective for long patterns and large alphabets.

For pattern ABC, the rightmost occurrence table contains:

Alignment at shift :

• Compare pattern character C at with text character A.
• They mismatch.
• The shift is .

Alignment at shift :

• Again, C is compared with A and mismatches.
• Shift by .

Alignment at shift :

• Compare C with C, B with B, and A with A.
• All comparisons succeed.

Therefore, the pattern occurs at index:

The algorithm reaches the match using large shifts instead of checking every possible alignment.

Selection:

• Brute force is suitable for small inputs or one-time searches where simplicity matters.
• KMP is suitable when a guaranteed linear bound is required or the text is repetitive.
• Boyer-Moore is often preferred for practical searches involving long patterns and large alphabets.

The algorithms differ mainly in how they use information obtained before a mismatch:

• Brute force: Discards all previous matching information. It shifts the pattern by one position and begins comparing from the pattern's first character.
• KMP: Uses the LPS array. If characters matched, it replaces with and preserves the longest useful prefix-suffix match. The text index does not move backward.
• Boyer-Moore: Compares right to left and may shift by several positions. It uses the mismatching text character through the bad-character rule and the already matched suffix through the good-suffix rule.

Thus, brute force performs no preprocessing, KMP uses information about pattern borders, and Boyer-Moore uses both alphabet-position and suffix information to obtain larger shifts.