Input: s ="hello world", T =["hello","world","test"]Output: [0,6,-1]Explanation:
-"hello"is found at index 0in"hello world"-"world"is found at index 6in"hello world"-"test"is not found in"hello world", so return-1
Example 2:
1
2
3
4
5
6
Input: s ="algorithm design", T =["algo","design","thesis"]Output: [0,10,-1]Explanation:
-"algo"is found at index 0in"algorithm design"-"design"is found at index 10in"algorithm design"-"thesis"is not found in"algorithm design", so return-1
We have plethora of options - String Pattern Search/Matching Algorithm Index. Assuming you have a significant number of smaller strings, Rabin-Karp is the standard way to search for multiple small strings in a very very large string. if You only have a few smaller strings, simply repeating Boyer-Moore for each one might be a better alternative.
To solve this problem, we will iterate through each string in the array T and check if it is a substring of s. If it is found, we will return the starting index; otherwise, return -1.
⏰ Time complexity: O(n * m), where n is the number of strings in T and m is the length of the string s. Finding a substring takes O(m) time in the worst case.
🧺 Space complexity: O(n) as we need to store the result for each string in T.
Read more about suffix tree. We can first get all the suffices of s and check for each element t in T to see if t is the beginning part of any suffix. To make this more efficient, we can build a suffix tree and perform the operations.
For example, s = "mississippi"; T = { "is", "sip", "hi", "sis" }.
The suffices of s
[0]
“mississippi”
[1]
“ississippi”
[2]
“ssissippi”
[3]
“sissippi”
[4]
“issippi”
[5]
“ssippi”
[6]
“sippi”
[7]
“ippi”
[8]
“ppi”
[9]
“pi”
[10]
“i”
Then for “is” in T, we see it starts at the beginning of suffixes [1] and [4]. For “sip”, we see it in [6]. We do not see “hi” in the suffixes, but we do see “sis” in [3].
⏰ Time complexity: O(n + m + k), where n is the length of the string s, m is the number of strings in T, and k is the total length of all strings in T. Building the suffix tree takes O(n), and each search operation takes O(m + k).
🧺 Space complexity: O(n) for storing the suffix tree.