HomeSubjectsUniversityBlogAbout

String Algorithms

Topic in Data Structures & Algorithms

210 total MCQsShowing 30 with explanations10 Easy10 Medium10 Hard
Start Timed Quiz on String AlgorithmsBack to Data Structures & Algorithms

About This Topic

String algorithms process sequences of characters to find patterns, compare texts or extract structure, with pattern matching being the most common task. Questions contrast the naive O(nm) matcher with Knuth-Morris-Pratt, which uses a prefix function or failure table to avoid rescanning, and Rabin-Karp, which relies on a rolling hash and must handle spurious hits. Boyer-Moore's bad-character and good-suffix rules and the Z-algorithm also appear. Multi-pattern search with Aho-Corasick extends KMP into an automaton. Other items cover suffix arrays and the LCP array, palindromes via dynamic programming or Manacher's linear-time algorithm, and edit distance, for example between kitten and sitting.

Below are 30 practice questions from a pool of 210 String Algorithms MCQs, one of 12 topics in Data Structures & Algorithms. Each shows the correct answer with an explanation; when you are ready, take a timed quiz to test recall under exam conditions.

Practice Questions

Each question below shows the correct answer with a full explanation. Use these to build conceptual understanding before attempting a timed quiz.

String AlgorithmsEasy

Q1. What is string matching?

  1. A.Comparing two strings for equality only
  2. B.Finding occurrences of a pattern in text✓ Correct
  3. C.Sorting strings in alphabetical order
  4. D.Concatenating two strings end to end

Explanation

String matching (pattern matching) is the problem of finding all occurrences of a pattern string within a larger text string.

Report an error in this question

String AlgorithmsEasy

Q2. What is the brute force string matching time complexity for text of length n and pattern of length m?

  1. A.O(n)
  2. B.O(n + m)
  3. C.O(m)
  4. D.O(n × m)✓ Correct

Explanation

Brute force string matching checks the pattern at every position in the text, giving O(n × m) worst-case time complexity.

Report an error in this question

String AlgorithmsEasy

Q3. What is a suffix of a string?

  1. A.A substring starting from the beginning
  2. B.A rotated version of the string
  3. C.The first character of the string
  4. D.A substring ending at the last character✓ Correct

Explanation

A suffix is a substring that ends at the last character. For 'hello', suffixes include 'o', 'lo', 'llo', 'ello', 'hello'.

Report an error in this question

String AlgorithmsEasy

Q4. What is a substring?

  1. A.A rearrangement of string characters
  2. B.A contiguous sequence of characters within a string✓ Correct
  3. C.A string of exactly length 1 character
  4. D.Any characters from a string in any order

Explanation

A substring is a contiguous sequence of characters within a string. For example, 'bcd' is a substring of 'abcde'.

Report an error in this question

String AlgorithmsEasy

Q5. What is string concatenation?

  1. A.Splitting a string into parts
  2. B.Reversing a string entirely
  3. C.Joining two strings end to end✓ Correct
  4. D.Sorting characters in a string

Explanation

String concatenation joins two or more strings end to end to form a new string. For example, 'hello' + ' world' = 'hello world'.

Report an error in this question

String AlgorithmsEasy

Q6. What is a palindrome?

  1. A.A string with only repeated characters throughout
  2. B.A string with all unique characters
  3. C.A string with an even number of characters
  4. D.A string that reads the same forward and backward✓ Correct

Explanation

A palindrome is a string that reads the same forward and backward, such as 'racecar' or 'madam'.

Report an error in this question

String AlgorithmsMedium

Q7. What is the KMP (Knuth-Morris-Pratt) algorithm?

  1. A.A string compression algorithm for reducing text size
  2. B.A hash-based search method for substring matching tasks
  3. C.A pattern matcher using failure function to skip redundancy✓ Correct
  4. D.A comparison-based sorting algorithm for string arrays

Explanation

KMP preprocesses the pattern to build a failure function (partial match table) that allows it to skip redundant comparisons, achieving O(n + m) time.

Report an error in this question

String AlgorithmsEasy

Q8. What is a prefix of a string?

  1. A.The middle portion of the string
  2. B.A reversed version of the string
  3. C.The last character of the string
  4. D.A substring starting from the beginning✓ Correct

Explanation

A prefix is a substring that starts at the beginning of the string. For 'hello', prefixes include 'h', 'he', 'hel', 'hell', 'hello'.

Report an error in this question

String AlgorithmsEasy

Q9. What is an anagram?

  1. A.A palindrome of another word
  2. B.A prefix of another given word
  3. C.A substring of another word
  4. D.A rearrangement forming another word✓ Correct

Explanation

An anagram is formed by rearranging the characters of a word to create a new word, using all original letters exactly once (e.g., 'listen' and 'silent').

Report an error in this question

String AlgorithmsEasy

Q10. What is a subsequence of a string?

  1. A.A sequence derived by deleting characters keeping order✓ Correct
  2. B.A contiguous part of the original string
  3. C.A sorted version of the original string
  4. D.A reversed version of the original string

Explanation

A subsequence is formed by deleting zero or more characters from a string without changing the relative order of remaining characters.

Report an error in this question

String AlgorithmsEasy

Q11. How can you check if two strings are anagrams?

  1. A.Compare their lengths only for equality
  2. B.Check if they have the same first character
  3. C.Reverse one string and compare with the other
  4. D.Sort both strings and compare, or count frequencies✓ Correct

Explanation

Two strings are anagrams if they have the same character frequencies. This can be checked by sorting both (O(n log n)) or counting character frequencies (O(n)).

Report an error in this question

String AlgorithmsMedium

Q12. What is the longest palindromic substring problem?

  1. A.Finding the longest string in a collection
  2. B.Reversing a string to find palindromes
  3. C.Finding the longest contiguous palindrome substring✓ Correct
  4. D.Finding all palindromes in a given string

Explanation

The problem asks for the longest contiguous substring of a given string that reads the same forwards and backwards.

Report an error in this question

String AlgorithmsMedium

Q13. What is the Rabin-Karp algorithm?

  1. A.A divide and conquer string matching algorithm
  2. B.A string matching algorithm using rolling hashes✓ Correct
  3. C.A string sorting algorithm by character values
  4. D.A tree-based matching algorithm using tries

Explanation

Rabin-Karp uses a rolling hash to compute hash values of text substrings, comparing them with the pattern's hash for quick matching.

Report an error in this question

String AlgorithmsMedium

Q14. What is a rolling hash in Rabin-Karp?

  1. A.A hash that updates efficiently as the window slides✓ Correct
  2. B.A multi-level hash with cascading computation
  3. C.A hash that changes randomly each call
  4. D.A hash stored in a circular buffer structure

Explanation

A rolling hash efficiently updates the hash value when the window slides by one position, by removing the contribution of the outgoing character and adding the incoming one in O(1).

Report an error in this question

String AlgorithmsMedium

Q15. What is the time complexity of finding the longest palindromic substring using dynamic programming?

  1. A.O(n^3)
  2. B.O(n)
  3. C.O(n^2)✓ Correct
  4. D.O(n log n)

Explanation

The DP approach fills an n × n table, checking if each substring is a palindrome, taking O(n^2) time.

Report an error in this question

String AlgorithmsMedium

Q16. What is the time complexity of the KMP algorithm?

  1. A.O(n + m)✓ Correct
  2. B.O(m log n)
  3. C.O(n × m)
  4. D.O(n^2)

Explanation

KMP runs in O(n + m) time: O(m) for preprocessing the pattern and O(n) for searching through the text.

Report an error in this question

String AlgorithmsMedium

Q17. What is string hashing used for?

  1. A.Efficiently comparing strings via hash values✓ Correct
  2. B.Encrypting strings for secure storage
  3. C.Compressing strings to save disk space
  4. D.Sorting strings into alphabetical order

Explanation

String hashing computes hash values of strings for efficient comparison. It is used in pattern matching, duplicate detection, and many string problems.

Report an error in this question

String AlgorithmsMedium

Q18. What is the Boyer-Moore algorithm?

  1. A.A pattern matcher using bad character and good suffix rules✓ Correct
  2. B.A brute force matching algorithm for strings
  3. C.A string sorting algorithm by character frequency
  4. D.A compression algorithm for text data files

Explanation

Boyer-Moore compares the pattern from right to left and uses bad character and good suffix heuristics to skip portions of the text, often achieving sub-linear time in practice.

Report an error in this question

String AlgorithmsHard

Q19. What is the time complexity of the Boyer-Moore algorithm in the best case?

  1. A.O(n/m)✓ Correct
  2. B.O(n × m)
  3. C.O(n)
  4. D.O(n + m)

Explanation

In the best case, Boyer-Moore achieves O(n/m) time by skipping m characters at a time using the bad character heuristic.

Report an error in this question

String AlgorithmsHard

Q20. What is the number of distinct substrings of a string of length n?

  1. A.n(n+1)/2 minus sum(LCP)✓ Correct
  2. B.2^n (exponential count)
  3. C.n^2 (quadratic count)
  4. D.n! (factorial of n)

Explanation

The number of distinct substrings is n(n+1)/2 - sum(LCP), where LCP is the longest common prefix array of the suffix array. Total substrings minus duplicates.

Report an error in this question

String AlgorithmsHard

Q21. What is the Aho-Corasick algorithm?

  1. A.A multi-pattern matcher building a trie-based automaton✓ Correct
  2. B.A compression algorithm for pattern libraries
  3. C.A single pattern matching algorithm only
  4. D.A string sorting algorithm for multiple strings

Explanation

Aho-Corasick builds a trie-based automaton from multiple patterns and searches for all patterns simultaneously in the text in O(n + m + z) time, where z is the number of matches.

Report an error in this question

String AlgorithmsHard

Q22. What is a suffix automaton?

  1. A.An automaton that generates all suffixes
  2. B.A pattern matching machine for any text
  3. C.A minimal DFA recognizing all suffixes of a string✓ Correct
  4. D.A suffix tree variant with compressed nodes

Explanation

A suffix automaton is the smallest DFA that accepts exactly all suffixes of a string. It can be built in O(n) time and has at most 2n-1 states.

Report an error in this question

String AlgorithmsMedium

Q23. How is the Z-algorithm used for pattern matching?

  1. A.By hashing the pattern and comparing values
  2. B.By using a suffix tree of the text string
  3. C.By sorting the text characters first
  4. D.By concatenating pattern and text then computing Z-array✓ Correct

Explanation

The Z-algorithm concatenates pattern P, a separator, and text T (P$T), then computes the Z-array. Positions where Z[i] = |P| indicate pattern matches.

Report an error in this question

String AlgorithmsMedium

Q24. What is the Z-array of a string?

  1. A.An array where Z[i] is longest prefix match starting at i✓ Correct
  2. B.The reverse of the original string as array
  3. C.An array of character frequencies for the string
  4. D.An array of zeros for initialization

Explanation

The Z-array for a string S has Z[i] = length of the longest substring starting at position i that is also a prefix of S. It can be computed in O(n) time.

Report an error in this question

String AlgorithmsHard

Q25. What is the time complexity of building a suffix array using the DC3/skew algorithm?

  1. A.O(n log^2 n)
  2. B.O(n log n)
  3. C.O(n^2)
  4. D.O(n)✓ Correct

Explanation

The DC3 (difference cover) algorithm constructs a suffix array in O(n) time, which is optimal.

Report an error in this question

String AlgorithmsHard

Q26. What is the LCP (Longest Common Prefix) array?

  1. A.An array storing longest common prefix lengths between consecutive sorted suffixes✓ Correct
  2. B.An array storing character frequencies found within a given string
  3. C.An array storing the lengths of all strings within a collection
  4. D.An array storing prefix sums computed over numeric data elements

Explanation

The LCP array stores the length of the longest common prefix between consecutive suffixes in the suffix array, useful for many string problems.

Report an error in this question

String AlgorithmsHard

Q27. What is polynomial string hashing?

  1. A.Hashing using polynomial long division
  2. B.Computing hash as sum of characters times powers of a base✓ Correct
  3. C.Hashing that produces polynomial-length hash output
  4. D.Using polynomial time algorithms for hash computation

Explanation

Polynomial hashing computes hash(s) = s[0]×p^0 + s[1]×p^1 + ... + s[n-1]×p^(n-1) mod M, where p is a prime base. It supports efficient rolling hash computation.

Report an error in this question

String AlgorithmsHard

Q28. What is the longest repeated substring problem's optimal solution?

  1. A.O(n^3) brute force approach
  2. B.O(n^2) using dynamic programming
  3. C.O(n log^2 n) using rolling hashing
  4. D.O(n) using suffix array with LCP array✓ Correct

Explanation

The longest repeated substring can be found in O(n) time by building a suffix array and LCP array, then finding the maximum value in the LCP array.

Report an error in this question

String AlgorithmsHard

Q29. What is Manacher's algorithm?

  1. A.A string sorting algorithm for arrays
  2. B.A pattern matching algorithm for text
  3. C.A string compression algorithm for storage
  4. D.An O(n) algorithm finding all palindromic substrings✓ Correct

Explanation

Manacher's algorithm finds the longest palindromic substring (and all maximal palindromes) in O(n) time by cleverly reusing previously computed palindrome information.

Report an error in this question

String AlgorithmsHard

Q30. What is Burrows-Wheeler Transform (BWT)?

  1. A.A string matching algorithm for patterns
  2. B.A reversible transformation aiding text compression✓ Correct
  3. C.A string encryption method for security
  4. D.A hash function designed for string data

Explanation

BWT rearranges characters of a string by sorting all rotations, producing output with more character runs. It is reversible and used in bzip2 compression.

Report an error in this question

More Data Structures & Algorithms Topics

Foundations of DS & Algorithms

Practice MCQs with explanations

Linear Data Structures

Practice MCQs with explanations

Non-Linear Data Structures

Practice MCQs with explanations

Searching Algorithms

Practice MCQs with explanations

Sorting Algorithms

Practice MCQs with explanations

Hashing

Practice MCQs with explanations

Ready to test yourself on String Algorithms?

Take a timed quiz drawn from 210+ questions on this topic. No signup required — your progress saves in your browser.

Start String Algorithms Quiz