Ninja's Frustrating Homework

Ninja
0/200
Average time to solve is 60m
profile
Contributed by
10 upvotes
Asked in companies
CodenationIncedo Inc.

Problem statement

Ninja got a summer vacation homework in which he got a booklet containing a very long string and some set of words written in his diary for which he had to search all these words in that string booklet.

His teacher asked him to write all the starting indices for all the words written in the diary after searching that from the string booklet.

Ninja finds this work very frustrating. He tries to find some help from his neighbor and currently, you are the one who is his neighbor.

It is very time consuming to find every word in the string booklet manually. So you decide to design a code for that. Help Ninja!

Note :

Follow 0 based indexing. 
Print the indices in sorted order.
Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line of input contains an integer ‘T’, which denotes the number of test cases. Then each test case follows.

The first line of each test case contains a string ‘S’ representing the string in the booklet.

The second line of each test case contains an integer N denoting the number of words in the diary.

The third line of each test case contains an array of strings of size ‘N’ representing the words in the diary.

Output Format :

The output contains ‘N’ space-separated integers representing starting indices of ‘N’ number of words present in the diary.

Note:

You don't need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= |S| <= 1000
1 <= N <= 30

Where |S| denotes the length of the given string ‘S’.
Sample Input 1 :
2
abcab
3
a cab abca
ninjasmart
3
jas art nin
Sample Output 1:
0 1 2
0 3 7
Explanation for Sample Input 1:
Test Case 1 :
The given string is “abcab”. The word “a” is present in the string starting from index 0 and ending at index 0, The word “cab” has starting index 2 and ending index 4 , “abca” has starting index 0 ending index 3.

Test Case 2:
The given string is “ninjasmart”. “Jas” has starting index 3 ending index 5, “art” has starting index 8 ending index 10, “nin” has starting index 0 ending index 2.
Sample Input 2:
2
ahishers
4
he she his hers
bheythis
2
hey this
Sample Output 2:
1 3 4 4
1 4
Hint

Try to search matches for every character of word in ‘diary’ in the ‘booklet’ string naively.

Approaches (2)
Brute Force

The idea is to slide every word in ‘diary’ over ‘booklet’ string one by one and check for a match. If a match is found, then slide by 1 to check for subsequent matches.

Approach :

  • First store the length of ‘booklet’ in a variable‘bookletLength’.
  • Iterate the loop for all words of ‘diary’ with the help of an iterator pointer ‘i’.
    • Store the length of each word of ‘diary’ in a variable ‘wordLength’.
    • Make an iteration to slide the word of ‘diary’ one by one with the help of an iterator pointer ‘j’ from 0 to ‘bookletLength’ - ‘wordLength’.
      • For the current index ‘j’ check for pattern matching with an iteration from 0 to ‘wordLength’ with an iterator pointer ‘k’.
        • Check if booklet[j + k] is not equal to diary[i][k]. If this condition is true then exit the iteration.
      • Check if k = ‘wordLength’ then push the index ‘i’ into the vector ‘ans’.
  • Return ‘ans’ as the final answer.
Time Complexity

O(M * N * Z), Where ‘M’ is the length of the ‘booklet’ string, ‘N’ is the number of words in ‘diary’, ‘Z’ is the length of the longest word from the ‘diary’.

 

As we are using 3 nested iterations to search for a match for every word in ‘diary’. Therefore, overall time complexity will be O(M * N * Z).

Space Complexity

O(1)

 

As constant space is used. Therefore, the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Ninja's Frustrating Homework
Full screen
Console