Assignment 5 Ancient Fax Machine Solution

Description



Mahir has a really old fax machine. He is using this fax machine to communicate with his friends and family. But one day this machine starts glitching. As a result all of the space characters in the messages are skipped by the machine. As an example, if a friend sends Mahir the message "the cake is a lie", the fax machine will print it as "thecakeisalie". After some time this starts causing him problems since he cannot know where words start or end for sure. The message "dragon y" might mean "dragon y", "dragon y" or "drag on y". After struggling with these messages Mahir decides to write a program that can calculate how many ways are there to split a message printed by this fax machine into words.












Input/Output



You will be given a message and a list of possible words that can appear in the message. You are asked to print out in how many ways that a given message can be interpreted.




2.1 Input Format




The rst line of the input le contains the received message as a string. Second line of the input le is an integer D, specifying the number of words in Mahir’s dictionary. Each of the following D lines contain a string, a distinct word in the dictionary. The dictionary does not have to be in the alphabetical order. A word in the dictionary might not appear in the message.




2.2 Output Format




Your program should calculate and print out the number of possible split-tings of this message into words, using the words the given dictionary. This number can be really big, so you should calculate it in modulo 109 + 7. One of the biggest prime numbers that can t into a 32 bit integer.




Hint: Whenever you perform an arithmetic operation, use long long int data type and take the modulo afterwards. This will prevent arithmetic over ow and ensure you get the right answer.








2.3 Example Input 1




hellomahir




3




hello




world




mahir










2.4 Example Output 2




1




This message can only be interpreted as "hello mahir".




2.5 Example Input 2




thisisoverusedcarsalesman




14




ale




ales




car




cars




is




man




over




overused




ruse




sale




sales




salesman




this




used










2.6 Example Output 2




6




All possible ways to interpret this message:




this is overused car salesman




this is overused cars ales man




this is over used car sales man




this is over used car salesman




this is over used cars ales man





2.7 Example Input 3




aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa




32




a




aa




aaa




aaaa




aaaaa




aaaaaa




aaaaaaa




aaaaaaaa




aaaaaaaaa




aaaaaaaaaa




aaaaaaaaaaa




aaaaaaaaaaaa




aaaaaaaaaaaaa




aaaaaaaaaaaaaa




aaaaaaaaaaaaaaa




aaaaaaaaaaaaaaaa




aaaaaaaaaaaaaaaaa




aaaaaaaaaaaaaaaaaa




aaaaaaaaaaaaaaaaaaa




aaaaaaaaaaaaaaaaaaaa




aaaaaaaaaaaaaaaaaaaaa




aaaaaaaaaaaaaaaaaaaaaa




aaaaaaaaaaaaaaaaaaaaaaa




aaaaaaaaaaaaaaaaaaaaaaaa




aaaaaaaaaaaaaaaaaaaaaaaaa




aaaaaaaaaaaaaaaaaaaaaaaaaa




aaaaaaaaaaaaaaaaaaaaaaaaaaa




aaaaaaaaaaaaaaaaaaaaaaaaaaaa




aaaaaaaaaaaaaaaaaaaaaaaaaaaaa




aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa




aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa




aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa





2.8 Example Output 2




147483634




Since this message can be split on each possible location, the number of pos-sible interpretations of this message is 231 = 2; 147; 483; 648. 2; 147; 483; 648 modulo 1; 000; 000; 009 is 147; 483; 634.







Grading



Grading of this project is based on the success of your code in test cases. Your nal score will be the sum of points from each test case. Each test case will have equal weight. Maximum score is 100.







Implementation Details



Variable limits are as follows:



1 Length of the received message 1,000




1 Number of words in the dictionary 1,000




1 Length of each word in the dictionary 1,000




All of the characters in each string will be a lower case letter.




Execution time limit is 1 seconds. If your code runs more than 1 seconds on a test case you will get 0 points from that test case. This project is all about optimizing your solution. Before starting with your code, consider the time complexity of your algorithm. If you can realize your algorithm is a slow one before you start coding, it can save you time.



Your program will be compiled with cmake CMakeLists.txt && make command and executed with ./project5 inputFile output-File command.






Warnings



Make sure an executable is created after executing cmake CMake-Lists.txt && make commands. Otherwise your code will fail in grad-ing.









5