Back to Subject

Unit 8: Pattern Matching - Practice Quiz

ECAP538 60 Questions
0 Correct 0 Wrong 60 Left
0/60

1 What is the main goal of a pattern matching algorithm?

Design of algorithms for pattern matching problems Easy
A. To arrange the characters of a text alphabetically
B. To replace every character in a text
C. To find occurrences of a pattern in a text
D. To compress a text into a shorter form

2 In pattern matching, what does the term text usually mean?

Design of algorithms for pattern matching problems Easy
A. The larger sequence being searched
B. The table used during preprocessing
C. The result returned after sorting
D. The smaller sequence being located

3 In pattern matching, what is a pattern?

Design of algorithms for pattern matching problems Easy
A. The sequence being sorted
B. The sequence being divided
C. The sequence being encrypted
D. The sequence being searched for

4 If a text has length and a pattern has length , how many possible starting alignments exist when ?

Design of algorithms for pattern matching problems Easy
A.
B.
C.
D.

5 What does preprocessing a pattern mean?

Design of algorithms for pattern matching problems Easy
A. Deleting repeated characters before searching
B. Sorting all characters before searching
C. Joining the pattern to another text
D. Building information about the pattern before searching

6 How does the brute-force pattern matching algorithm search the text?

Brute-force algorithm Easy
A. It tests the pattern at each possible alignment
B. It sorts the text before testing the pattern
C. It divides the text into equal halves
D. It builds a tree from every text character

7 After a mismatch, how far does the basic brute-force algorithm usually shift the pattern?

Brute-force algorithm Easy
A. The full pattern
B. One position
C. Two positions
D. Half the pattern

8 What is the worst-case time complexity of brute-force pattern matching for text length and pattern length ?

Brute-force algorithm Easy
A.
B.
C.
D.

9 What preprocessing is required by the basic brute-force pattern matching algorithm?

Brute-force algorithm Easy
A. A bad-character table
B. A good-suffix table
C. No special preprocessing
D. An LPS table

10 When does brute-force pattern matching report a match at an alignment?

Brute-force algorithm Easy
A. When the first pattern character matches
B. When every pattern character matches
C. When half of the pattern characters match
D. When the final pattern character matches

11 What is the main advantage of the Knuth-Morris-Pratt algorithm?

Knuth-Morris-Pratt algorithm Easy
A. It avoids rechecking previously matched text characters
B. It converts the text into numeric values
C. It searches only the first half of the text
D. It sorts the pattern before each comparison

12 Which table is commonly constructed during KMP preprocessing?

Knuth-Morris-Pratt algorithm Easy
A. The routing table
B. The adjacency table
C. The LPS table
D. The frequency table

13 What does LPS stand for in the KMP algorithm?

Knuth-Morris-Pratt algorithm Easy
A. Longest Proper Prefix which is also a Suffix
B. Last Pattern Symbol within a Search
C. Lowest Pattern Shift within a String
D. Largest Possible Substring within a Sequence

14 What is the time complexity of KMP for a text of length and a pattern of length ?

Knuth-Morris-Pratt algorithm Easy
A.
B.
C.
D.

15 Which part of the input is used to build the KMP LPS table?

Knuth-Morris-Pratt algorithm Easy
A. The alphabet
B. The text
C. The output
D. The pattern

16 In which direction does Boyer-Moore typically compare pattern characters?

Boyer-Moore algorithm Easy
A. From left to right
B. From the center outward
C. From right to left
D. From both ends alternately

17 Which two heuristics are associated with the Boyer-Moore algorithm?

Boyer-Moore algorithm Easy
A. Greedy and divide-and-conquer heuristics
B. Hashing and dynamic-programming heuristics
C. Prefix and binary-search heuristics
D. Bad-character and good-suffix heuristics

18 What information does the bad-character heuristic use after a mismatch?

Boyer-Moore algorithm Easy
A. The length of the text alone
B. The total number of matches
C. The mismatching text character
D. The first character of the text

19 What information does the good-suffix heuristic use?

Boyer-Moore algorithm Easy
A. A prefix that was never compared
B. A suffix that matched before the mismatch
C. A character outside the current text
D. A sorted copy of the entire pattern

20 Why can Boyer-Moore be faster than brute-force matching in practice?

Boyer-Moore algorithm Easy
A. It sorts each alignment before comparison
B. It always compares every text character twice
C. It removes duplicate characters from the text
D. It can shift the pattern by multiple positions

21 A text has length and a pattern has length . How many valid alignments must an exact pattern-matching algorithm potentially examine?

Design of algorithms for pattern matching problems Medium
A.
B.
C.
D.

22 Which algorithm is most suitable when a text arrives as a stream and previously read text characters should not be revisited?

Design of algorithms for pattern matching problems Medium
A. Basic Boyer-Moore matching
B. Knuth-Morris-Pratt matching
C. An algorithm that stores every alignment and compares all of them after the stream ends
D. Brute-force matching

23 A case-insensitive matcher converts both the text and pattern to lowercase before searching. Why must the same normalization be applied to both?

Design of algorithms for pattern matching problems Medium
A. To eliminate repeated substrings from the text
B. To preserve consistent equality comparisons
C. To guarantee constant-time searching
D. To reduce the pattern length

24 If every occurrence, including overlapping occurrences, must be reported, what should a correct pattern-matching algorithm do after finding a match?

Design of algorithms for pattern matching problems Medium
A. Continue from a valid next alignment
B. Delete the matched text segment
C. Resume only after the end of the current matched substring, permanently excluding all overlaps
D. Stop immediately after the match

25 Using brute-force matching on the text AABAACAADAABAABA with pattern AABA, which zero-based starting positions are reported?

Brute-force algorithm Medium
A.
B.
C.
D.

26 A brute-force matcher reports all occurrences of pattern AAA in text AAAAAA. How many character comparisons does it perform if it compares the complete pattern at every valid alignment?

Brute-force algorithm Medium
A.
B.
C.
D.

27 What is the worst-case running time of brute-force pattern matching for text length and pattern length ?

Brute-force algorithm Medium
A.
B.
C.
D.

28 After a mismatch at an alignment, how does the standard brute-force algorithm choose the next alignment?

Brute-force algorithm Medium
A. It moves the pattern past the entire previously compared region
B. It shifts the pattern one position right
C. It uses the longest prefix table
D. It shifts according to the mismatched character

29 What is the LPS array for the pattern ABABAC?

Knuth-Morris-Pratt algorithm Medium
A.
B.
C.
D.

30 During KMP matching, five pattern characters have matched, but the next comparison fails. If the LPS value for the fifth matched character is , what happens next?

Knuth-Morris-Pratt algorithm Medium
A. The current alignment is discarded and the pattern is always moved beyond all five matched characters
B. The text pointer moves backward by
C. Matching resumes at pattern index
D. Matching resumes at pattern index

31 What does an LPS value of at pattern index mean?

Knuth-Morris-Pratt algorithm Medium
A. The next match begins at text index
B. Exactly mismatches occur before index
C. A length- proper prefix is also a suffix
D. A length- substring appears only once in the complete text

32 KMP searches for ABABCABAB in ABABDABACDABABCABAB. At which zero-based index does the pattern begin?

Knuth-Morris-Pratt algorithm Medium
A.
B.
C.
D.

33 After KMP finds AAA in AAAAA, which pattern index should it use next to detect overlapping matches?

Knuth-Morris-Pratt algorithm Medium
A.
B.
C.
D.

34 Including preprocessing, what is the asymptotic time complexity of KMP for a text of length and a pattern of length ?

Knuth-Morris-Pratt algorithm Medium
A.
B.
C.
D.

35 In which direction does the Boyer-Moore algorithm normally compare pattern characters at each alignment?

Boyer-Moore algorithm Medium
A. From right to left
B. From the middle outward
C. From left to right
D. In alphabetic order

36 For the pattern ALGORITHM, a mismatch occurs at pattern index against text character G. Using the bad-character rule and the rightmost G at pattern index , what shift is selected?

Boyer-Moore algorithm Medium
A.
B.
C.
D.

37 A Boyer-Moore mismatch occurs at pattern index , and the mismatched text character does not occur in the pattern. What shift does the bad-character rule permit?

Boyer-Moore algorithm Medium
A.
B. positions regardless of where the mismatch occurred
C.
D.

38 What information is used by the good-suffix rule after a mismatch?

Boyer-Moore algorithm Medium
A. The frequency of every pattern symbol across the entire input alphabet
B. The first occurrence of the mismatched character
C. The number of text characters already scanned
D. The suffix already matched at the alignment

39 If the bad-character rule suggests a shift of and the good-suffix rule suggests a shift of , what shift does standard Boyer-Moore apply?

Boyer-Moore algorithm Medium
A.
B.
C.
D.

40 Why can Boyer-Moore be especially effective on long patterns over a large alphabet?

Boyer-Moore algorithm Medium
A. It avoids preprocessing the pattern
B. Its running time is constant whenever every pattern character is distinct and the text is stored contiguously
C. Its heuristics can skip several alignments
D. It always performs exactly comparisons

41 Let have length , let have length , and form , where occurs in neither string. Using zero-based indices, if the prefix function of satisfies , what is the starting index of the corresponding match in ?

Design of algorithms for pattern matching problems Hard
A.
B.
C.
D.

42 For two nonempty strings and of equal length , which test correctly determines in time whether is a cyclic rotation of ?

Design of algorithms for pattern matching problems Hard
A. Search for in and accept a match ending before .
B. Search for in and accept any complete match.
C. Search for in and accept a match starting in .
D. Search for in and accept only a match starting at .

43 A text arrives in chunks whose boundaries may split an occurrence of the pattern. Which design reports every match in worst-case linear total time without retaining the complete text?

Design of algorithms for pattern matching problems Hard
A. Restart brute force at the beginning of every newly received text chunk.
B. Preserve KMP's matched-prefix length between chunks and preprocess the pattern once.
C. Run Boyer-Moore independently on each chunk and discard all boundary state.
D. Retain only the previous mismatch position and restart comparisons from that position.

44 Assume and arbitrary unstructured inputs. What is the optimal worst-case asymptotic time for reporting all occurrences of one length- pattern in a length- text?

Design of algorithms for pattern matching problems Hard
A. ; preprocessing is never required when the alphabet is finite.
B. ; both inputs may require inspection, and KMP attains this bound.
C. ; all text alignments can be inferred from the pattern alone.
D. ; each possible alignment must be checked independently.

45 An occurrence is formally defined by for every integer . Under this definition, how should an algorithm handle an empty pattern when the text has length ?

Design of algorithms for pattern matching problems Hard
A. Report all boundaries from position through position .
B. Report no occurrences because an empty pattern contains no symbols.
C. Report exactly one occurrence at position and terminate the search.
D. Report the first boundaries from position through position .

46 A left-to-right brute-force matcher searches for , where . How many character comparisons are performed when every alignment is examined?

Brute-force algorithm Hard
A.
B.
C.
D.

47 A left-to-right brute-force algorithm reports every match of in . Counting both successful and failed character tests, how many comparisons does it perform?

Brute-force algorithm Hard
A. comparisons
B. comparisons
C. comparisons
D. comparisons

48 Suppose text and pattern symbols are independent and uniformly distributed over an alphabet of size . What is the expected number of comparisons made by left-to-right brute force over all alignments?

Brute-force algorithm Hard
A.
B.
C.
D.

49 For and , compare left-to-right and right-to-left brute-force matching over all alignments. By what asymptotic factor can right-to-left matching perform more comparisons?

Brute-force algorithm Hard
A.
B.
C.
D.

50 After brute force finds a complete match, it shifts the pattern by rather than by one. For which patterns is this optimization guaranteed to preserve every occurrence in every possible text?

Brute-force algorithm Hard
A. Patterns having no nonempty proper prefix that is also a suffix.
B. Patterns whose symbols are arranged in nondecreasing alphabetic order.
C. Patterns whose first and final symbols are equal to each other.
D. Patterns having at least one symbol that occurs exactly once.

51 Using the convention that is the length of the longest proper prefix that is also a suffix of , what is the prefix array for ?

Knuth-Morris-Pratt algorithm Hard
A.
B.
C.
D.

52 For , KMP is in state , meaning that has matched. If the next text symbol is , what state does KMP enter after all necessary fallback operations?

Knuth-Morris-Pratt algorithm Hard
A.
B.
C.
D.

53 KMP searches for . Which result and post-match state are correct when overlapping occurrences must be reported?

Knuth-Morris-Pratt algorithm Hard
A. Report starts and set after each complete match.
B. Report starts and set after each match.
C. Report starts and set after each match.
D. Report starts and set after each complete match.

54 Which amortization fact is sufficient to prove that KMP's text scan takes time even though one text symbol may trigger several fallback operations?

Knuth-Morris-Pratt algorithm Hard
A. Every text symbol participates in exactly one pattern comparison.
B. Total fallback decreases of are bounded by prior increases of .
C. The prefix values are strictly increasing throughout preprocessing.
D. never decreases while the scan advances through the text.

55 For , the final prefix value is . Which sequence lists all nonempty proper border lengths from longest to shortest?

Knuth-Morris-Pratt algorithm Hard
A.
B.
C.
D.

56 In Boyer-Moore, let with zero-based indices. A mismatch occurs at pattern index , and the aligned text symbol is . What shift is proposed by the standard bad-character rule?

Boyer-Moore algorithm Hard
A. position
B. positions
C. positions
D. positions

57 After Boyer-Moore matches the suffix but mismatches at , which action describes the strong good-suffix rule?

Boyer-Moore algorithm Hard
A. Align the rightmost earlier preceded by a symbol different from ; otherwise align the longest suffix of that is a prefix of .
B. Align the rightmost earlier preceded by the same symbol as ; otherwise align the longest prefix of with a suffix of .
C. Ignore the matched suffix and shift according only to the last occurrence of the mismatching text symbol.
D. Align the leftmost earlier occurrence of regardless of its preceding symbol; otherwise shift the pattern by exactly one position.

58 After a complete match of , what shift does Boyer-Moore's good-suffix preprocessing prescribe to preserve overlapping matches?

Boyer-Moore algorithm Hard
A. positions
B. positions
C. positions
D. position

59 Consider Boyer-Moore using only the standard bad-character rule, scanning right to left. For and , what is its worst-case comparison count?

Boyer-Moore algorithm Hard
A.
B.
C.
D.

60 A bad-character-only Boyer-Moore search has and . At every alignment, the final pattern symbol mismatches a text symbol absent from the pattern, so each shift is . Exactly how many character comparisons occur?

Boyer-Moore algorithm Hard
A. comparisons
B. comparisons
C. comparisons
D. comparisons
Previous MCQ
Unit 7
Next MCQ
Unit 9