Unit 2: String Matching Algorithms and Computational Geometry - Subjective Questions

Sequential search, also called linear search, examines the elements of a collection one by one until the required key is found or the collection ends.

Algorithm:

1. Start with the first element of the array.
2. Compare the current element with the search key.
3. If they are equal, return the position of the element.
4. Otherwise, move to the next element.
5. If the end of the array is reached, report that the key is absent.

Pseudocode:

SequentialSearch(A, n, key)
    for i = 0 to n - 1
        if A[i] == key
            return i
    return -1

Complexity analysis:

• Best case: The key is the first element, so only one comparison is made: .
• Worst case: The key is the last element or is absent, requiring comparisons: .
• Average case: For a successful search with all positions equally likely, the expected number of comparisons is
  
  Therefore, the average-case complexity is .
• Space complexity: Only a constant amount of additional storage is needed, so it is .

Sequential search works with both sorted and unsorted data, but it is inefficient for large collections.

The sentinel technique removes the need to check the array boundary during every iteration of sequential search.

Method:

• Save the last array element.
• Place the search key in the last position as a sentinel.
• Scan the array until the key is encountered.
• Determine whether the key was found in its original position or only at the sentinel position.
• Restore the original last element.

Pseudocode:

SentinelSearch(A, n, key)
    last = A[n - 1]
    A[n - 1] = key
    i = 0
    while A[i] != key
        i = i + 1
    A[n - 1] = last
    if i < n - 1 or last == key
        return i
    return -1

Advantages:

• The loop performs only one condition check per iteration.
• It eliminates repeated tests such as inside the loop.
• It may reduce constant execution overhead.

Complexity:

• Best case:
• Worst case:
• Extra space:

The sentinel method does not change the asymptotic complexity, but it can make the implementation more efficient in practice.

The brute-force string-matching algorithm aligns the pattern with every possible position in the text and compares corresponding characters from left to right.

Let the text be and the pattern be .

Procedure:

1. Align the pattern at text position .
2. Compare with .
3. If all characters match, report shift .
4. If a mismatch occurs, shift the pattern by one position.
5. Repeat for all shifts from to .

There are possible alignments. In the worst case, all pattern characters are compared at every alignment. Therefore, the maximum number of comparisons is

Thus, the worst-case running time is

When is proportional to , this can become . The algorithm uses auxiliary space.

A typical worst case occurs when the text and pattern contain many repeated characters, causing the mismatch to happen only near the end of each alignment.

The naive pattern-matching algorithm checks the pattern at every valid shift of the text.

Pseudocode:

NaiveMatch(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

A shift is reported if

Overlapping occurrences:

After finding a match, the algorithm still increases the shift by only one. Therefore, it does not skip an occurrence that overlaps the previous one.

For example, for text AAAAA and pattern AAA, matches occur at shifts , , and . These occurrences overlap, but all are reported.

Complexity:

• Number of possible shifts:
• Worst-case time: , commonly written as
• Best-case time: when a mismatch occurs at the first character of every alignment
• Auxiliary space:

Sequential search and naive pattern matching both inspect data in order, but they solve different problems.

Sequential search can be regarded as searching for an object of unit size. Naive pattern matching is more expensive because a candidate position may require several character comparisons before a mismatch is discovered.

The Rabin-Karp algorithm uses hashing to compare the pattern with each length- substring of the text.

Let be the hash of the pattern and be the hash of the text window beginning at shift .

Steps:

1. Compute the hash of the pattern.
2. Compute the hash of the first text window of length .
3. For every valid shift :
   • If , the pattern cannot match at that shift.
   • If , compare the actual characters to verify the match.
   • Compute the hash of the next window using a rolling-hash formula.

Hash hit: A hash hit occurs when

It only indicates that the pattern and the text window have the same hash.

Valid match: A valid match occurs when the corresponding characters are also equal:

Two different strings may have the same hash; this is called a spurious hit or collision. Character-by-character verification prevents incorrect results.

Complexity:

• Preprocessing:
• Expected or average running time:
• Worst-case running time with many collisions:
• Auxiliary space: , excluding the output

Assume that characters are represented as digits in base , the pattern length is , and computations are performed modulo a prime .

The hash of the text window beginning at shift is

Define

To obtain the next window hash, first remove the contribution of the outgoing character :

Shift the remaining characters one base position to the left by multiplying by :

Finally, add the incoming character and take the modulus:

Meaning of the terms:

• : Size of the character alphabet or chosen hash base
• : Modulus, usually a prime used to keep hash values small
• : Weight of the leftmost character
• : Contribution of the outgoing character
• : Incoming character of the next window

If the computed value is negative in an implementation, is added to normalize it into the range through .

Because the next hash is calculated from the previous hash in constant time, all text-window hashes can be processed in time, excluding collision verification.

Rabin-Karp performs an initial computation for the pattern hash and the first text-window hash. Each subsequent rolling-hash update takes time.

Expected performance:

• There are text windows.
• Hash values usually differ, so most windows are rejected without character comparison.
• With a good hash function and a sufficiently large prime modulus, collisions are rare.
• The expected running time is therefore
  

Worst-case performance:

If every text window has the same hash as the pattern, the algorithm verifies up to characters at every shift. The running time then becomes

This can happen because of a poor modulus, an unsuitable hash function, or adversarial input producing many collisions.

Rabin-Karp is particularly useful when:

• Several patterns of the same length must be searched in one text.
• Pattern hashes can be stored in a hash table for efficient membership tests.
• Plagiarism detection or document fingerprinting is required.
• Two-dimensional pattern matching is performed.
• Approximate filtering is needed before exact verification.

Its major advantage is the ability to compare fingerprints efficiently, while its major limitation is the possibility of collisions.

The LPS array stores, for each pattern prefix ending at position , the length of its longest proper prefix that is also a suffix.

A proper prefix cannot be the entire substring itself. If the pattern is , then LPS[i] is the largest value such that

For the pattern ABABCABAB:

Thus, the LPS array is

KMP uses this information after a mismatch to avoid rechecking characters that are already known to match.

The Knuth-Morris-Pratt (KMP) algorithm searches a text using structural information about the pattern. It preprocesses the pattern into an LPS array and uses this array to determine how far the pattern can be shifted after a mismatch.

Let be the text index and the pattern index.

Search procedure:

1. If , increment both and .
2. If , report a match at and set to search for overlapping matches.
3. If a mismatch occurs and , set
   
   without moving backward.
4. If a mismatch occurs and , increment .

Why comparisons are not repeated:

Suppose pattern characters have matched. The LPS value identifies the longest suffix of the matched portion that is also a pattern prefix. These characters need not be compared again. The pattern is repositioned so that this prefix aligns with the known matching suffix.

Complexity proof:

• Building the LPS array takes time.
• During searching, never decreases and can be incremented at most times.
• A fallback decreases , and the total number of increments and fallbacks of is linear.
• Therefore, the search phase takes time.

Hence, the total running time is

The LPS array requires additional space.

The LPS array is constructed by maintaining the length of the longest prefix-suffix found for the previously processed position.

Let len be the current candidate prefix length and let be the position being processed.

Algorithm:

BuildLPS(P)
    m = length(P)
    LPS[0] = 0
    len = 0
    i = 1
    while i < m
        if P[i] == P[len]
            len = len + 1
            LPS[i] = len
            i = i + 1
        else if len > 0
            len = LPS[len - 1]
        else
            LPS[i] = 0
            i = i + 1
    return LPS

Explanation:

• If , the current prefix-suffix can be extended.
• If the characters differ and len is positive, the algorithm tries the next shorter valid prefix using LPS[len - 1].
• If len is zero, no nonempty proper prefix-suffix exists for that position.

Time complexity:

Although an iteration may reduce len without increasing , len cannot be increased or decreased indefinitely. Across the entire algorithm, the total number of such changes is linear. Every character participates in only a constant amortized number of operations. Therefore, LPS construction takes time and uses space for the array.

The three algorithms solve exact string matching but use different strategies.

Selection guidelines:

• Use naive matching when the text or pattern is small and simplicity is important.
• Use Rabin-Karp when hashing is beneficial, especially for many equal-length patterns.
• Use KMP when deterministic performance is required or when the input contains many repeated characters.

Different string-processing tasks require different data structures.

• Character arrays or strings:

  • Store characters contiguously.
  • Provide indexed access.
  • Exact comparison or scanning may require time.
  • Suitable for direct implementation of standard matching algorithms.

• Hash tables:

  • Store complete strings or string fingerprints.
  • Provide expected lookup after the string's hash has been computed.
  • Hashing a string of length normally costs .
  • Collisions must be handled.

• Tries:

  • Store strings character by character along root-to-node paths.
  • Search, insertion, and deletion take time.
  • Efficient for prefix queries but may consume significant memory.

• Suffix trees:

  • Compressed tries of all suffixes of a text.
  • Support pattern search in time after construction.
  • Can occupy substantial memory and are complex to implement.

• Suffix arrays:

  • Store starting positions of suffixes in lexicographically sorted order.
  • Use less memory than suffix trees.
  • Pattern search can be performed using binary search, commonly in time without additional optimizations.

The appropriate structure depends on whether the application requires exact lookup, prefix lookup, substring search, memory efficiency, or dynamic updates.

A trie, or prefix tree, is a rooted tree used to store a set of strings. Each edge represents a character, and the path from the root to a node represents a prefix. A terminal marker indicates that a complete word ends at a node.

Insertion of a word of length :

1. Start at the root.
2. For each character, follow the corresponding child edge.
3. If the edge does not exist, create a new node.
4. Mark the final node as terminal.

Time complexity: .

Search:

1. Start at the root and follow one edge for each character.
2. If an edge is missing, the word is absent.
3. After all characters are processed, the word exists only if the final node is marked terminal.

Time complexity: .

Deletion:

1. Follow the path of the word.
2. Remove its terminal marker.
3. Delete nodes from the end while they have no children and are not terminal nodes for another word.
4. Preserve nodes shared with other words.

Time complexity: .

The operation times depend primarily on the word length rather than on the number of words stored. The main disadvantage is potentially high memory usage due to child pointers.

To find all words beginning with a prefix of length , a trie first follows the path corresponding to the prefix.

• If any required edge is missing, no stored word has that prefix.
• If the prefix node is reached, a depth-first or breadth-first traversal of its subtree reports all matching words.
• Reaching the prefix node takes time.
• Reporting results requires additional time proportional to the visited output characters or nodes.

This makes a trie suitable for autocomplete, dictionary lookup, spell-checking, and routing based on prefixes.

Array-based node representation:

• Every node stores an array of child pointers of size , where is the alphabet.
• Child access is usually .
• It is simple and fast for small fixed alphabets.
• Space usage can be high because many array entries may be null.

Map-based node representation:

• Each node stores only the children that exist.
• A hash map gives expected child access.
• A balanced search tree gives child access and ordered traversal.
• It saves space for sparse nodes and large alphabets but has additional map overhead.

Array-based nodes favor speed, while map-based nodes favor memory efficiency and alphabet flexibility.

The closest-pair problem asks for two distinct points in a set of points whose Euclidean distance is minimum.

For points and , their distance is

Brute-force solution:

1. Initialize the minimum distance to infinity.
2. Generate every unordered pair of distinct points.
3. Compute the distance between each pair.
4. Update the minimum distance and closest pair whenever a smaller distance is found.

The number of unordered pairs is

Therefore, the time complexity is . The auxiliary space is if the points are stored in the input array.

In implementation, squared distances can be compared:

This avoids repeatedly computing square roots while preserving the ordering of distances. The brute-force approach is simple and is effective for small input sets.

The divide-and-conquer closest-pair algorithm improves on the brute-force method.

Algorithm:

1. Sort the points by their -coordinates.
2. Divide the set into left and right halves using the median -coordinate.
3. Recursively find the closest pair in each half.
4. Let
   
   where and are the minimum distances in the two halves.
5. Construct a vertical strip containing points whose horizontal distance from the dividing line is less than .
6. Process the strip in increasing -coordinate order.
7. For each strip point, compare it only with a constant number of following points, commonly at most seven.
8. Return the smallest distance found in either half or across the strip.

If points sorted by are maintained through recursive calls, dividing and merging the ordered lists and checking the strip require time at each recursion level.

The recurrence is

Using the Master Theorem,

The initial sorting also takes , so the total complexity remains . Typical auxiliary space is .

After the recursive calls, every pair entirely within the left half or entirely within the right half is known to be at least apart. Only pairs crossing the dividing line can improve the answer.

The strip contains points within horizontal distance of the dividing line and is processed in increasing -coordinate order.

Consider a rectangle of width and height above a strip point. Divide it into small regions, commonly squares of side . If too many points were placed in this rectangle, two points belonging to the same recursive half would have distance less than , contradicting the definition of .

This packing argument limits the number of possible nearby points. In the standard two-dimensional proof, each point needs to be compared with at most the next seven points in -sorted order.

Therefore:

• Points with vertical separation at least can be ignored.
• Only a constant number of later points are potential closer partners.
• The entire strip can be checked in time rather than time.

This geometric bound is the key reason the divide-and-conquer algorithm achieves total time.

The convex hull of a finite set of planar points is the smallest convex set containing all the points. Intuitively, it is the polygon formed by stretching a rubber band around the outermost points.

A set is convex if, for every pair of points and in the set, the entire line segment joining them also lies in the set.

Important properties:

• Convex-hull vertices are points from the original input set.
• Interior points do not become hull vertices.
• The hull is unique as a geometric set.
• For non-collinear input, the boundary forms a convex polygon.
• If all points are collinear, the hull degenerates to a line segment between the two extreme points.
• The vertices can be reported in clockwise or counterclockwise order.
• For points, the hull contains at most vertices.

Applications:

• Shape analysis and object recognition
• Collision detection in computer graphics
• Geographic information systems
• Robotics and motion planning
• Determining the diameter of a point set
• Separating point sets in pattern recognition
• Constructing bounding regions for spatial data

Convex-hull algorithms are fundamental tools in computational geometry and are often used as preprocessing steps for other geometric problems.

The Graham scan constructs the convex hull by sorting points by polar angle and removing points that create non-convex turns.

Orientation test:

For three points , , and , compute

• If the value is positive, form a counterclockwise turn.
• If it is negative, they form a clockwise turn.
• If it is zero, they are collinear.

Graham scan procedure:

1. Select the point with the smallest -coordinate; break ties using the smallest -coordinate.
2. Sort the remaining points by polar angle around .
3. Handle equal-angle points consistently, usually retaining the farthest one if boundary-collinear points are not required.
4. Push the initial points onto a stack.
5. Process each remaining point :
   • Examine the top two stack points and .
   • While do not form the required counterclockwise turn, pop .
   • Push .
6. The final stack contains the convex-hull vertices in counterclockwise order.

Complexity:

• Finding the pivot:
• Sorting by polar angle:
• Stack scan: , because every point is pushed once and popped at most once

Thus, the total running time is

The stack requires auxiliary space in the worst case.