Avalg homework 1 fall 2001
Questions and answers


Q: When counting the number of strings matching a pattern, should we count the number of MATCHES or the number of MATCHING STRINGS?

Consider the string "abbc" and the pattern "a*b*c". There are two matches, b can match either the first or the second b, but there is only one string that matches, namely "abbc".

A: You should count the number of matching strings. I've changed the text in the exercise to remove the ambiguity.

Q: Look at the pattern "ab" and the string "abab". What are the number of matching substrings?

A: 2.

Q: Look at the pattern "a*" and the string "abc". What are the number of matching substrings?

A: 3.

Q: I've found a solution with worst-case time complexity Omega(n*n), where n is the length of the string. Is that good enough?

A: For a full score you will need to find a better algorithm. It's not likely that a quadratic algorithm will meet the time bounds for strings containing 1,000,000 characters.

Q: We have a question about the "longest repeated substring". Does this mean the longest substring that occurs at least two times or does it mean the longest substring that repeats itself, as in "abcabc".

A: It's the longest substring that occurs at least twice.

Q: Look at the string "AABB" and the pattern "A*B". Can the string that matches * contain the characters 'A' and 'B'? Is the answer 1 or 4?

A: The '*' character matches _any_ string. There are 4 matching substrings in your example.




Stefan Nilsson
2001-11-30