Oct 23, 2023
Let \( dp[i] \) be the maximum number of vowels you can obtain after assembling the first \( i \) characters into complete words. Try to come up with an algorithm that obtains \( dp[|M|] \) in \( O(|M|\sum_i|W_i|) \), where \( M \) is the message and \( W \) are the words.
We notice that intuitively, there cannot be many words if every word is very long, and there cannot be very long words if there are many words. Can we formalize this observation and achieve \( O(|M|\sqrt{\sum_i|W_i|}) \) complexity?
Let \( dp[i][j] \) be the number of ways to create a string of length \( i \) that matches to the \( j \)-th state in the KMP algorithm, assuming whatever matches the whole string \( p \) just loops in the termination state. Can we come up with an algorithm that solves \( dp[n][|p|] \) in \( O(n|p|) \)?
Can we accelerate the algorithm?