Unit 5: Naive Pattern Search - Practice Quiz

1 In the naïve pattern searching algorithm, the pattern is compared with the text starting at every possible position. What is the worst-case time complexity for a text of length and pattern of length ?

2 How many starting positions in the text does the naïve algorithm check for a text of length and pattern of length ?

3 What is the overall time complexity of the KMP (Knuth-Morris-Pratt) pattern matching algorithm for text length and pattern length ?

4 What auxiliary structure does the KMP algorithm precompute from the pattern to avoid redundant comparisons?

5 Which technique is central to the Rabin-Karp pattern matching algorithm?

6 In Rabin-Karp, when two substrings produce the same hash value but the actual characters differ, this event is called a:

7 What is the average-case time complexity of the Rabin-Karp algorithm for text length and pattern length ?

8 A suffix array of a string stores which of the following?

9 How many suffixes does a string of length have?

10 A common trick to check if string is a rotation of string is to verify that is a substring of:

11 For two strings to possibly be rotations of each other, what must first be true?

12 Which traversal techniques are commonly used to find the largest connected component in a grid?

13 In a grid problem using 4-directional connectivity, a cell is connected to its neighbors in how many directions?

14 If pattern occurs somewhere inside text , then is called a __ of .

15 Is the empty string "" considered a substring of every string?

16 For the string "", what is the longest proper prefix that is also a suffix?

17 When computing the longest prefix which is also a suffix, why must it be a proper prefix/suffix?

18 Using naïve search, how many times does the pattern "" occur in the text ""?

19 Which of the following lists is in correct lexicographical (dictionary) order?

20 Splitting the string "" on the delimiter "" produces how many substrings?

21 For a text of length and a pattern of length , what is the worst-case time complexity of the naïve pattern search algorithm?

22 Which text-pattern pair triggers the worst-case behavior of naïve pattern matching?

23 In the KMP algorithm, what does the LPS (Longest Prefix Suffix) array store for each index of the pattern?

24 What is the overall time complexity of the KMP algorithm for text length and pattern length ?

25 For the pattern ABABAA, what is the correct LPS array?

26 In the Rabin-Karp algorithm, why is a hash comparison alone insufficient to confirm a pattern match?

27 What is the key advantage of using a rolling hash in Rabin-Karp?

28 What is the average-case time complexity of Rabin-Karp for text length and pattern length with a good hash?

29 What does a suffix array of a string store?

30 For the string banana, which suffix comes first in its suffix array?

31 A common trick checks if string B is a rotation of A by testing whether B is a substring of which string?

32 Which pair of strings are rotations of each other?

33 Which technique is most commonly used to find the largest connected component of cells in a grid?

34 For a grid with rows and columns using 4-directional connectivity, what is the time complexity of a flood-fill solution?

35 Using naïve substring checking, how many starting positions must be examined when searching pattern of length in text of length ?

36 Which statement about the empty string as a pattern is correct?

37 For the string aabaaab, what is the length of the longest proper prefix that is also a suffix?

38 The 'longest prefix which is also a suffix' concept is directly used to build which structure?

39 To count all overlapping occurrences of a pattern in a text using naïve search, what should you do after finding a match at index ?

40 When sorting the strings ["apple", "app", "apply"] lexicographically, what is the correct order?

41 Consider naïve pattern searching of a pattern of length in a text of length . What text/pattern combination triggers the algorithm's absolute worst-case number of character comparisons?

42 For the pattern $P = $ aabaabaaa, what is the KMP failure/LPS array (longest proper prefix that is also suffix for each prefix)?

43 During KMP matching, when a mismatch occurs at pattern index (with ), what is the correct next action?

44 In Rabin-Karp with a rolling hash, why can the worst-case time complexity degrade to despite the rolling hash being per shift?

45 For rolling hash , the update when sliding one position removes the leading char and adds trailing . Which formula is correct?

46 For the string $S = $ banana, what is the suffix array (starting indices, 0-based, sorted lexicographically)?

47 Using the fastest practical construction (prefix-doubling with radix sort), what is the time complexity to build a suffix array for a string of length ?

48 The standard trick to test if is a rotation of (equal lengths ) is to check whether is a substring of . Using KMP, what is the time and space complexity?

49 Given $A = $ abcde, which of the following is NOT a rotation of ?

50 For finding the largest connected component of 1s in an binary grid using DFS/BFS with 8-directional connectivity, what is the correct time complexity?

51 When using a Union-Find (DSU) approach to compute the largest connected component in a grid, why is it sufficient to union each cell only with its right and bottom neighbors (for 4-connectivity)?

52 You must check if pattern ( chars) is a substring of text ( chars) with guaranteed worst-case linear time AND no risk of false positives from hashing. Which algorithm best fits?

53 For $S = $ abababab, what is the length of the longest proper prefix that is also a suffix?

54 The smallest period of a string of length equals , where is the longest proper prefix-suffix length. For $S = $ aabaaab (length 7) with , what is the smallest period, and does the string have a period dividing ?

55 You want to count overlapping occurrences of pattern in text using naïve search. After a match at position , how should the search index advance to correctly count overlaps?

56 Given text aaaaa and pattern aa, how many overlapping occurrences exist, and how many non-overlapping (greedy left-to-right) occurrences exist?

57 To arrange a list of numbers as strings so their concatenation forms the largest possible number, which comparator should sort two strings and ?

58 When sorting the strings ["3", "30", "34", "5", "9"] to form the largest number, what is the resulting concatenation?

59 Consider partitioning a string of length into contiguous substrings such that each substring is a palindrome, and you want the minimum number of cuts. What is the time complexity of the standard DP solution?

60 You must count the number of ways to split a binary string into non-empty substrings such that each part, read as binary, is a power of . Which algorithmic technique most directly gives an efficient solution?