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 compress a text into a shorter form
B. To arrange the characters of a text alphabetically
C. To replace every character in a text
D. To find occurrences of a pattern in a text

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

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

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 searched for
D. The sequence being encrypted

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. Sorting all characters before searching
B. Deleting repeated characters before searching
C. Building information about the pattern before searching
D. Joining the pattern to another text

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

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

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

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

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 good-suffix table
B. An LPS table
C. A bad-character table
D. No special preprocessing

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 half of the pattern characters match
C. When every pattern character matches
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 sorts the pattern before each comparison
C. It searches only the first half of the text
D. It converts the text into numeric values

12 Which table is commonly constructed during KMP preprocessing?

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

13 What does LPS stand for in the KMP algorithm?

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

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 output
B. The pattern
C. The text
D. The alphabet

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

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

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

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

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

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

19 What information does the good-suffix heuristic use?

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

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

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

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. Brute-force matching
B. Basic Boyer-Moore matching
C. An algorithm that stores every alignment and compares all of them after the stream ends
D. Knuth-Morris-Pratt 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 reduce the pattern length
B. To guarantee constant-time searching
C. To eliminate repeated substrings from the text
D. To preserve consistent equality comparisons

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. Stop immediately after the match
B. Delete the matched text segment
C. Continue from a valid next alignment
D. Resume only after the end of the current matched substring, permanently excluding all overlaps

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 according to the mismatched character
C. It shifts the pattern one position right
D. It uses the longest prefix table

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. Matching resumes at pattern index
B. The text pointer moves backward by
C. Matching resumes at pattern index
D. The current alignment is discarded and the pattern is always moved beyond all five matched characters

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

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

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 left to right
B. From right to left
C. From the middle outward
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 number of text characters already scanned
C. The first occurrence of the mismatched character
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 always performs exactly comparisons
B. It avoids preprocessing the pattern
C. Its heuristics can skip several alignments
D. Its running time is constant whenever every pattern character is distinct and the text is stored contiguously

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 starting in .
B. Search for in and accept only a match starting at .
C. Search for in and accept any complete match.
D. Search for in and accept a match ending before .

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. Retain only the previous mismatch position and restart comparisons from that position.
C. Preserve KMP's matched-prefix length between chunks and preprocess the pattern once.
D. Run Boyer-Moore independently on each chunk and discard all boundary state.

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. ; all text alignments can be inferred from the pattern alone.
B. ; preprocessing is never required when the alphabet is finite.
C. ; both inputs may require inspection, and KMP attains this bound.
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 the first boundaries from position through position .
B. Report exactly one occurrence at position and terminate the search.
C. Report no occurrences because an empty pattern contains no symbols.
D. Report all 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 whose first and final symbols are equal to each other.
B. Patterns having no nonempty proper prefix that is also a suffix.
C. Patterns having at least one symbol that occurs exactly once.
D. Patterns whose symbols are arranged in nondecreasing alphabetic order.

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 complete match.
D. Report starts and set after each 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. never decreases while the scan advances through the text.
B. Every text symbol participates in exactly one pattern comparison.
C. Total fallback decreases of are bounded by prior increases of .
D. The prefix values are strictly increasing throughout preprocessing.

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. positions
B. position
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 leftmost earlier occurrence of regardless of its preceding symbol; otherwise shift the pattern by exactly one position.
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 rightmost earlier preceded by a symbol different from ; otherwise align the longest suffix of that is a prefix of .

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. position
C. positions
D. positions

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