Question: Given a paragraph of text, write a program to find the first shortest sub - segment that contains each of the given k words at

Given a paragraph of text, write a program to find the first shortest sub-segment that contains each of the given k words at least once. A segment is said to be shorter than other if it contains less number of words.
Ignore characters other than [a-z][A-Z] in the text. Comparison between the strings should be case-insensitive.
If no sub-segment is found, then the program should display NO SUBSEGMENT FOUND.
Input format :
First line of the input contains the text.
Next line contains k , the number of words to be searched.
Each of the next k lines contains a word.
Output format :
Print first shortest sub-segment that contains given k words , ignore special characters, numbers. If no sub-segment is found, print NO SUBSEGMENT FOUND
Sample Input :
This is a test. This is a programming test. This is a programming test in any language.
4
this
a
test
programming
Sample Output :
a programming test This
Explanation :
Here, segment "a programming test. This" contains given four words. You have to print without special characters or numbers. So output is "a programming test This". Another segment "This is a programming test." also contains the given four words, but has more number of words.
Constraint :
Total number of characters in a paragraph will not be more than 200,000.
0< k <= no. of words in paragraph.
0< Each word length <15

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!