What is the main drawback of the naive string matching algorithm when searching for a pattern in a text?
Think about how many comparisons the naive method might do in the worst case.
The naive algorithm checks for the pattern at every position in the text, which can lead to many repeated comparisons, resulting in a worst-case time complexity of O(n*m), where n is the text length and m is the pattern length.
Given the text "abracadabra" and the pattern "cada", what will be the output of a function that returns the starting index of the first occurrence of the pattern in the text, or -1 if not found?
text = "abracadabra" pattern = "cada" # Function returns index or -1 result = text.find(pattern) print(result)
Look carefully at where the pattern starts in the text.
The substring "cada" starts at index 4 in "abracadabra" (0-based indexing), so the function returns 4.
Which string matching algorithm improves efficiency by using information from previous character comparisons to avoid unnecessary re-checks?
Consider which algorithm uses a prefix table to skip ahead.
The KMP algorithm preprocesses the pattern to create a prefix table that helps it skip unnecessary comparisons, improving efficiency over naive methods.
How many times does the pattern "ana" appear in the text "banana" when overlapping matches are counted?
Check for matches starting at each character, including overlaps.
The pattern "ana" appears twice in "banana": starting at index 1 and index 3 (0-based), counting overlapping occurrences.
Consider a pattern matching function that supports the wildcard character "?" which matches any single character. Given the text "abcdefg" and the pattern "a?c?e?g", what is the output of the function that returns true if the pattern matches the text exactly, and false otherwise?
Check each character match considering that '?' can match any single character.
The pattern "a?c?e?g" matches the text "abcdefg" because each '?' matches the characters 'b', 'd', and 'f' respectively, resulting in a full match.