New update is available. Click here to update.

Ninja and Index Pairs

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:

Declare a list/vector ‘allIndexPair’ as discussed above.
Run a loop on the ‘WORDS’ array/list:
- If the current word is present in the ‘TEXT’ string:
  - Add all these indexes in ‘allIndexPair’.
Sort this ‘allIndexPair’ according to the first element of the pair.
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).

Try Problem

Approach 2

The basic idea of this approach is to store all values of the ‘WORDS’ in a Trie ‘trie’.

Then we can find all the pairs of the given word by simply iterating on the ‘trie’.

The steps are as follows:

TrieNode class/struct:
- Make an array of ‘children’ and a variable ‘isEnd’ in which we store the current word ends at that node or not.
indexPairs(‘TEXT’ , ‘WORDS’):
- Make a node ‘trie’ of the class/struct TrieNode.
- Run a loop on the ‘WORDS’ array/list:
  - Make a TrieNode ‘curr’ and store ‘trie’.
  - Run a loop for ‘i’ = 0 to the length of the ‘word’:
    - ‘index”’= ‘word[i]’ - ‘a’.
    - If ‘curr.children[‘index’]’ is equal to ‘NULL’:
      1. Add a new ‘TrieNode’ node at this ’curr’ node.
    - ‘curr’ is equal to ‘curr.children[index].
  - ‘curr’.isEnd = true.
- Declare a list/vector ‘allIndexPair’ as discussed above.
- Run a loop for ‘i’ = 0 to the length of the string ‘TEXT’:
  - Call a function hasPrefix(‘TEXT’, ‘i’) it returns all the prefixes which are starting from ‘i’ in ‘TEXT’ and we store these into a list/vector ‘endIndcies’.
  - We run a loop for ‘j’ = 0 to the length of ‘endIndcies’:
    - Add (‘i’, ‘endIndcies[j]’) into ‘allIndexPair’.
- Finally, return ‘allIndexPair’.
hasPrefix(‘word’, ‘i’):
- Declare a variable ‘endIndcies’ in which we store all ‘endIndices’ of the given prefix.
- Make a TrieNode ‘curr’ and store ‘trie’.
- Run a loop for ‘i’ = 0 to the length of the ‘word’:
  - ‘index’ = ‘word’ - ‘a’.
  - If ‘curr.children[‘index’]’ is equal to ‘NULL’:
    - Break.
  - ‘curr’ is equal to ‘curr.children[index].
  - If ‘curr’.isEnd equal to true:
    - Add ‘i’ into ‘endIndices’.
- Finally, return ‘endIndices’.