$29
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.
1
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