Ninja and Index Pairs

Last Updated: 14 Apr, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Ninja has been given a string ‘TEXT’ and an array/list of strings ‘WORDS’ of size ‘N’. Ninja has to print all index pairs (‘i’, ‘j’) such that the substring of ‘TEXT’ is present in the ‘WORDS’.

Note:
``````Ninja has to return all the index pairs (‘i’, ‘j’) in sorted order, i.e., sort them by the first element of the pair, i.e., ‘i’.
``````
Input Format:
``````The first line contains a single integer ‘T’ representing the number of test cases.

The first line of each test case will contain a single space-separated string ‘TEXT’ which represents the value of ‘TEXT’.

The next line of each test case contains a single space-separated integer ‘N’ denoting the size of ‘WORDS’.

The next line of each test case contains ‘N’ space-separated integers representing the values of ‘WORDS’.
``````
Output Format:
``````For each test case, print all index pairs (‘i’, ‘j’) such that the substring of ‘TEXT’ is present in the ‘WORDS’ in sorted order according to the first element of the pair.

Output for every test case will be printed in a separate line.
``````
Note:
``````You don’t need to print anything; It has already been taken care of.
``````
Constraints:
``````1 <= ‘T’ <= 50
1 <= | ‘TEXT’ | <= 100
1 <= ‘N’ <= 20
1 <= |’WORDS[i]’ | <= 50

Where ‘T’ is the number of test cases, 'N' is the size of array/vector ‘WORDS’, |’WORDS[i]’| represents the size of each word in ‘WORDS’ and |’TEXT’| represents the size of input string ‘TEXT’|.

Time limit: 1 sec
``````

Approach 1

The basic idea is to first iterate on the ‘WORDS’ array/list and then for each word check in the string ‘TEXT’ whether this string is present or not. If the word is present then put all indexes in a list/vector ‘allIndexPair’ and at the end sort this list/vector and return this.

The steps are as follows:

1. Declare a list/vector ‘allIndexPair’ as discussed above.
2. Run a loop on the ‘WORDS’ array/list:
• If the current word is present in the ‘TEXT’ string:
• Add all these indexes in ‘allIndexPair’.
3. Sort this ‘allIndexPair’ according to the first element of the pair.
4. Finally, return the ‘allIndexPair’.

For example:

‘TEXT’ = “aaa”

‘WORDS’ = [a aa aaa]

For string “a’ indices are (0,0), (1,1), (2,2).

For string “aa’ indices are (0,1), (1,2).

For string “aaa’ indices are (0,2).