Intuition:
The optimal solution includes forming the LPS array using an optimized approach. To optimize the LPS computation, we must:
- Avoid recomputing prefix-suffix matches from scratch for every index.
- Use previously computed LPS values to efficiently extend the matches.
The key idea will be two use two pointers - i and j:
- i: Iterates through the string.
- j: Tracks the length of the longest prefix which is also a suffix.
Now, there can be two scenarios when we compare s[i] and s[j], where s is the combined string formed. Let us understand both the scenarios in detail.
Scenario 1: When s[i] == s[j]
Consider the following example:
Assume that we have already computed the LPS array for the indices 0 to 4. Now, we are at index 5 (i == 5) and we want to find LPS[5].
Understanding:
- i and j represents that the prefix of string s (s[0...j-1]) matches with the suffix of the string s[0...i-1]. (Since "a" matches as prefix as well as suffix in "abca", thus j = 1, which is length of "a")
- Now if we found s[i] and s[j] to be equal, this means the next character in the prefix (s[j]) is also matching with the next character in the suffix (s[i]).
-
Hence, we increase both j and i, indicating that the prefix-suffix match is now longer by one character. Thus, setting LPS[i] = j+1.
Thus, If
s[i] == s[j], it means that we have successfully extended an existing prefix-suffix match.
Scenario 2: When s[i] != s[j]
If
s[i] ≠ s[j], we need to backtrack j without resetting it to 0 immediately. Instead, we use LPS[j-1] to find the next possible matching prefix.
Why backtrack to LPS[j-1]?
The value
LPS[j-1] tells us the longest proper prefix that is also a suffix of the prefix ending at index j-1. If s[i] does not match s[j], then instead of rechecking from j = 0, we can check from
LPS[j-1].
Consider the following example:
Assume that we have already computed the LPS array for the indices 0 to 4. Now, we are at index 5 (i == 5) and we want to find LPS[5].
Understanding:
- Here, LPS[2] = 1 means that the longest prefix which is also a suffix till index 2 is "a" (having length 1).
- So we check if the next best prefix match can be extended from j = 1 instead of restarting j from 0.
Thus, if
s[i] != s[j], it means that we must backtrack j to
LPS[j-1] to find the next possible matching prefix. This leverages the previously computed LPS values to avoid redundant comparisons.
Approach:
- Combine Pattern and Text using a delimiter forming a combined string. Compute the LPS array for the combined string. To compute the LPS array:
- Initialize the LPS array with the first value as 0 and a pointer (j) to track the length of the longest prefix suffix.
- Traverse the string and compare the current character with the character at the tracked position.
- If they match, extend the prefix-suffix length by updating the LPS value and moving both pointers forward.
- If they do not match and the tracked position is greater than 0, backtrack using the previously computed LPS value.
- If no match is found after backtracking, set the LPS value to 0 and move to the next character.
- Iterate through the portion of the combined string corresponding to the text. If the LPS value equals the length of the pattern, it signifies a match at the corresponding position in the text.
- Store the indices where the pattern matches and return the result.
Solution:
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Compute the Longest prefix suffix array for the combined string
vector<int> computeLPS(string s) {
int n = s.size(); // size of string
// To store the longest prefix suffix
vector<int> LPS(n, 0);
int i = 1, j = 0;
// Iterate on the string
while(i < n) {
// If the character matches
if(s[i] == s[j]) {
LPS[i] = j+1;
i++, j++;
}
// Otherwise
else {
// Trace back j pointer till it does not match
while(j > 0 && s[i] != s[j]) {
j = LPS[j-1];
}
// If a match is found
if(s[i] == s[j]) {
LPS[i] = j+1;
j++;
}
i += 1;
}
}
return LPS; // Return the computed LPS array
}
public:
// Function to find all indices of pattern in text
vector<int> search(string pattern, string text) {
string s = pattern + '$' + text; // Combined string
// Function call to find the Z array for the combined string
vector<int> LPS = computeLPS(s);
// Length of pattern and text
int n = text.size(), m = pattern.size();
// To store the result
vector<int> ans;
// Iterate on the combined string after the delimiter
for(int i = m+1; i < s.size(); i++) {
if(LPS[i] == m) ans.push_back(i - 2*m);
}
return ans;
}
};
int main() {
string text = "xyzabxyzabxyz";
string pattern = "xyz";
// Creating an instance of the solution class
Solution sol;
// Function call to find all indices of pattern in text
vector<int> ans = sol.search(pattern, text);
for(auto ind : ans) cout << ind << " ";
return 0;
}
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
import java.util.*;
class Solution {
// Compute the Longest prefix suffix array for the combined string
private int[] computeLPS(String s) {
int n = s.length(); // size of string
// To store the longest prefix suffix
int[] LPS = new int[n];
int i = 1, j = 0;
// Iterate on the string
while (i < n) {
// If the character matches
if (s.charAt(i) == s.charAt(j)) {
LPS[i] = j + 1;
i++;
j++;
}
// Otherwise
else {
// Trace back j pointer till it does not match
while (j > 0 && s.charAt(i) != s.charAt(j)) {
j = LPS[j - 1];
}
// If a match is found
if (s.charAt(i) == s.charAt(j)) {
LPS[i] = j + 1;
j++;
}
i += 1;
}
}
return LPS; // Return the computed LPS array
}
// Function to find all indices of pattern in text
public List<Integer> search(String pattern, String text) {
String s = pattern + '$' + text; // Combined string
// Function call to find the LPS array for the combined string
int[] LPS = computeLPS(s);
// Length of pattern and text
int n = text.length(), m = pattern.length();
// To store the result
List<Integer> ans = new ArrayList<>();
// Iterate on the combined string after the delimiter
for (int i = m + 1; i < s.length(); i++) {
if (LPS[i] == m) ans.add(i - 2 * m);
}
return ans;
}
}
class Main {
public static void main(String[] args) {
String text = "xyzabxyzabxyz";
String pattern = "xyz";
// Creating an instance of the solution class
Solution sol = new Solution();
// Function call to find all indices of pattern in text
List<Integer> ans = sol.search(pattern, text);
for (int ind : ans) System.out.print(ind + " ");
}
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566
class Solution:
# Compute the Longest prefix suffix array for the combined string
def computeLPS(self, s):
n = len(s) # size of string
# To store the longest prefix suffix
LPS = [0] * n
i, j = 1, 0
# Iterate on the string
while i < n:
# If the character matches
if s[i] == s[j]:
LPS[i] = j + 1
i += 1
j += 1
# Otherwise
else:
# Trace back j pointer till it does not match
while j > 0 and s[i] != s[j]:
j = LPS[j - 1]
# If a match is found
if s[i] == s[j]:
LPS[i] = j + 1
j += 1
i += 1
return LPS # Return the computed LPS array
# Function to find all indices of pattern in text
def search(self, pattern, text):
s = pattern + '$' + text # Combined string
# Function call to find the LPS array for the combined string
LPS = self.computeLPS(s)
# Length of pattern and text
n, m = len(text), len(pattern)
# To store the result
ans = []
# Iterate on the combined string after the delimiter
for i in range(m + 1, len(s)):
if LPS[i] == m:
ans.append(i - 2 * m)
return ans
if __name__ == "__main__":
text = "xyzabxyzabxyz"
pattern = "xyz"
# Creating an instance of the solution class
sol = Solution()
# Function call to find all indices of pattern in text
ans = sol.search(pattern, text)
print(*ans)
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172
class Solution {
// Compute the Longest prefix suffix array for the combined string
computeLPS(s) {
let n = s.length; // size of string
// To store the longest prefix suffix
let LPS = new Array(n).fill(0);
let i = 1, j = 0;
// Iterate on the string
while (i < n) {
// If the character matches
if (s[i] === s[j]) {
LPS[i] = j + 1;
i++;
j++;
}
// Otherwise
else {
// Trace back j pointer till it does not match
while (j > 0 && s[i] !== s[j]) {
j = LPS[j - 1];
}
// If a match is found
if (s[i] === s[j]) {
LPS[i] = j + 1;
j++;
}
i += 1;
}
}
return LPS; // Return the computed LPS array
}
// Function to find all indices of pattern in text
search(pattern, text) {
let s = pattern + '$' + text; // Combined string
// Function call to find the LPS array for the combined string
let LPS = this.computeLPS(s);
// Length of pattern and text
let n = text.length, m = pattern.length;
// To store the result
let ans = [];
// Iterate on the combined string after the delimiter
for (let i = m + 1; i < s.length; i++) {
if (LPS[i] === m) ans.push(i - 2 * m);
}
return ans;
}
}
// Main Execution
let text = "xyzabxyzabxyz";
let pattern = "xyz";
// Creating an instance of the solution class
let sol = new Solution();
// Function call to find all indices of pattern in text
let ans = sol.search(pattern, text);
console.log(...ans);
Complexity Analysis:
Time Complexity: O(N), where N is the length of the combined string
Computing the LPS array takes O(N) time:
- The function iterates over the string (s) using i, which goes from 1 to N.
- Inside the loop:
- If s[i] == s[j], both i and j are incremented → Constant time operation.
- If s[i] != s[j], j is backtracked using LPS[j-1] inside a while loop.
Note that the total number of backtracking steps (decrementing j via LPS[j-1]) across all iterations is
at most n because:
- Each decrement follows a previous increment of j, meaning j moves forward and backward at most n times.
- This ensures that the while loop runs in amortized O(1) time per character.
Finding the matches requires iterating on the LPS taking O(N) time. Thus, the overall time complexity is O(N).
Space Complexity: O(N), to store the LPS array.