5 Christmas songs (exam 2015) You are putting together a set of Christmas songs that will...

Transcribed Image Text:

5 Christmas songs (exam 2015) You are putting together a set of Christmas songs that will be handed out at the Christmas party. The Dean has declared that every song must contain the sentence "Merry_Christmas_Dear_Dean", where "," denotes a blank space. E.g. the song: We wish you a Merry Christmasu We wish you a Merry Christmasu We wish you a Merry Christmasu Dear Dean Dear Dean contains one occurrence of of the sentence "Merry_Christmas Dear Dean" (line breaks are disregarded). 1 Algorithms and Data Structures 2 Weekplan String matching Formally, you are given a set S of songs S1,...,S, and a sentence P. Song S, contains n, characters and P contains m characters. Let n =E=, denote the total number of characters in the songs. All the strings are over an alphabet of size 0(1). Describe an algorithm that returns all the songs that contain P. Analyze the asymptotic running time of your algorithm. Remember to argue that your algorithm is correct. si%3D1 5 Christmas songs (exam 2015) You are putting together a set of Christmas songs that will be handed out at the Christmas party. The Dean has declared that every song must contain the sentence "Merry_Christmas_Dear_Dean", where "," denotes a blank space. E.g. the song: We wish you a Merry Christmasu We wish you a Merry Christmasu We wish you a Merry Christmasu Dear Dean Dear Dean contains one occurrence of of the sentence "Merry_Christmas Dear Dean" (line breaks are disregarded). 1 Algorithms and Data Structures 2 Weekplan String matching Formally, you are given a set S of songs S1,...,S, and a sentence P. Song S, contains n, characters and P contains m characters. Let n =E=, denote the total number of characters in the songs. All the strings are over an alphabet of size 0(1). Describe an algorithm that returns all the songs that contain P. Analyze the asymptotic running time of your algorithm. Remember to argue that your algorithm is correct. si%3D1

Answer rating: 100% (QA)

Code include include using namespace std void algorithmvector songs string P vecto... View the full answer