Prefix Function and KMP Algorithm for Competitive Programming
The prefix function is a string matching technique used in computer science and string algorithms. It efficiently computes an array that represents the length of the longest proper prefix which is also a suffix for each prefix of a given string. The Knuth-Morris-Pratt (KMP) algorithm utilizes the prefix function to perform pattern matching in linear time, making it an efficient algorithm for searching occurrences of a pattern within a text.
Table of Content
- What is KMP Algorithm?
- What is Prefix Function in KMP Algorithm?
- Use Cases of Prefix Function and KMP Algorithm in Competitive Programming
- Practice Problems of KMP Algorithm for Competitive Programming
What is KMP Algorithm?
Knuth–Morris–Pratt (KMP) Algorithm is a linear time string searching algorithm that efficiently finds occurrences of a pattern within a text.
What is Prefix Function in KMP Algorithm?
The Prefix Function is an integral part of the Knuth–Morris–Pratt Algorithm.
The prefix function for a string s is an array , where is the length of the longest proper prefix of the substring which is also a suffix of this substring. Proper prefix of a string is a prefix that is not equal to the string itself. It is obvious that because a string of length has no proper prefixes.
Examples:
Example 1: s=”xyzxyz
x"
Prefix Function for s will be=[0,0,0,1,2,3,4]Example 2: s=”xxyxxxy”
Prefix Function for s will be=[0,1,0,1,2,2,3]
Find Prefix Function (O(N3) approach):
The idea is to do the following: For all i from 0 to N-1, try all possible lengths for the prefix/suffix, with each comparison taking O(N) time.
Below is the implementation of above approach:
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// Function to compute the Prefix Function using an O(N^3) approach
vector<int> prefixFunction(string s) {
int n = s.length();
vector<int> pi(n, 0);
// Iterate through each position in the string
for (int i = 0; i < n; i++) {
// Try all possible lengths for the prefix/suffix
for (int j = 0; j < i; j++) {
// Check if the substrings are equal
if (s.substr(0, j + 1) == s.substr(i - j, j + 1)) {
pi[i] = j + 1; // If equal, update the value at the current position
}
}
}
// Return the computed Prefix Function
return pi;
}
// Driver Code
int main() {
string s = "abcabcabc";
vector<int> result = prefixFunction(s);
// Print the Prefix Function values
for (int val : result) {
cout << val << " ";
}
cout << endl;
return 0;
}
import java.util.ArrayList;
import java.util.List;
public class PrefixFunction {
// Function to compute the Prefix Function using an O(N^3) approach
public static List<Integer> prefixFunction(String s) {
int n = s.length();
List<Integer> pi = new ArrayList<>(n);
// Iterate through each position in the string
for (int i = 0; i < n; i++) {
pi.add(0); // Initialize the value at the current position
// Try all possible lengths for the prefix/suffix
for (int j = 0; j < i; j++) {
// Check if the substrings are equal
if (s.substring(0, j + 1).equals(s.substring(i - j, i + 1))) {
pi.set(i, j + 1); // If equal, update the value at the current position
}
}
}
// Return the computed Prefix Function
return pi;
}
// Driver Code
public static void main(String[] args) {
String s = "abcabcabc";
List<Integer> result = prefixFunction(s);
// Print the Prefix Function values
for (int val : result) {
System.out.print(val + " ");
}
System.out.println();
}
}
// This code is contributed by akshitaguprzj3
# Function to compute the Prefix Function using an O(N^3) approach
def prefix_function(s):
n = len(s)
pi = [0] * n
# Iterate through each position in the string
for i in range(n):
pi[i] = 0 # Initialize the value at the current position
# Try all possible lengths for the prefix/suffix
for j in range(i):
# Check if the substrings are equal
if s[:j + 1] == s[i - j:i + 1]:
pi[i] = j + 1 # If equal, update the value at the current position
# Return the computed Prefix Function
return pi
# Driver Code
if __name__ == "__main__":
s = "abcabcabc"
result = prefix_function(s)
# Print the Prefix Function values in a single line
print(*result)
// Function to compute the Prefix Function using an O(N^3) approach
function prefixFunction(s) {
const n = s.length;
const pi = new Array(n).fill(0);
// Iterate through each position in the string
for (let i = 0; i < n; i++) {
pi[i] = 0; // Initialize the value at the current position
// Try all possible lengths for the prefix/suffix
for (let j = 0; j < i; j++) {
// Check if the substrings are equal
if (s.substring(0, j + 1) === s.substring(i - j, i + 1)) {
pi[i] = j + 1; // If equal, update the value at the current position
}
}
}
// Return the computed Prefix Function
return pi;
}
// Driver Code
const s = "abcabcabc";
const result = prefixFunction(s);
// Print the Prefix Function values in a single line
console.log(result.join(" "));
Output
0 0 0 1 2 3 4 5 6
Find Prefix Function in O(N2) time:
It can be observed that . This can be proved by contradiction. If \pi[i]+1 " title="Rendered by QuickLaTeX.com" height="27" width="203" style="vertical-align: 26px;">, then we can take the suffix of length that is ending at index i+1, remove the last character from it, then we get a better suffix of length ending at position i, which is better than the value , which leads to a contradiction. Now since the value of prefix function can increase by at most 1, this means the function can grow at most N times and it can only decrease for at most N times too. So total no. comparisons can be 2*N, which gives a complexity of O(N2).
Below is the implementation of above approach:
#include <iostream>
#include <vector>
#include <string>
std::vector<int> prefix_function(const std::string& s) {
int n = s.size();
std::vector<int> pi(n, 0); // Initialize an array to store the prefix function values
// Iterate through each position in the string starting from the second character
for (int i = 1; i < n; ++i) {
int j = pi[i - 1]; // Initialize j with the previous prefix function value
// Iterate backwards through possible lengths for the prefix/suffix
while (j > 0 && s[j] != s[i]) {
j = pi[j - 1]; // Update j based on the previous prefix function value
}
// Check if the substrings are equal
if (s[j] == s[i]) {
++j; // If equal, update the value of j
}
pi[i] = j; // Update the prefix function value at the current position
}
// Return the computed Prefix Function
return pi;
}
int main() {
// Example usage:
std::string s = "xyzxyzx";
std::vector<int> result = prefix_function(s);
std::cout << "Prefix Function:";
for (int value : result) {
std::cout << " " << value;
}
std::cout << std::endl;
return 0;
}
import java.util.Arrays;
public class PrefixFunction {
static int[] prefixFunction(String s) {
int n = s.length();
int[] pi = new int[n]; // Initialize an array to store the prefix function values
// Iterate through each position in the string starting from the second character
for (int i = 1; i < n; i++) {
int j = pi[i - 1]; // Initialize j with the previous prefix function value
// Iterate backwards through possible lengths for the prefix/suffix
while (j > 0 && s.charAt(j) != s.charAt(i)) {
j = pi[j - 1]; // Update j based on the previous prefix function value
}
// Check if the substrings are equal
if (s.charAt(j) == s.charAt(i)) {
j++; // If equal, update the value of j
}
pi[i] = j; // Update the prefix function value at the current position
}
// Return the computed Prefix Function
return pi;
}
public static void main(String[] args) {
String s = "xyzxyzx";
int[] result = prefixFunction(s);
System.out.println("Prefix Function: " + Arrays.toString(result));
}
}
def prefix_function(s):
n = len(s)
pi = [0] * n # Initialize an array to store the prefix function values
# Iterate through each position in the string starting from the second character
for i in range(1, n):
j = pi[i - 1] # Initialize j with the previous prefix function value
# Iterate backwards through possible lengths for the prefix/suffix
while j > 0 and s[j] != s[i]:
j = pi[j - 1] # Update j based on the previous prefix function value
# Check if the substrings are equal
if s[j] == s[i]:
j += 1 # If equal, update the value of j
pi[i] = j # Update the prefix function value at the current position
# Return the computed Prefix Function
return pi
# Example usage:
s = "xyzxyzx"
result = prefix_function(s)
print("Prefix Function:", result)
function prefixFunction(s) {
const n = s.length;
const pi = new Array(n).fill(0); // Initialize an array to store the prefix function
//values
// Iterate through each position in the string starting from the second character
for (let i = 1; i < n; ++i) {
let j = pi[i - 1]; // Initialize j with the previous prefix function value
// Iterate backwards through possible lengths for the prefix/suffix
while (j > 0 && s[j] !== s[i]) {
j = pi[j - 1]; // Update j based on the previous prefix function value
}
// Check if the substrings are equal
if (s[j] === s[i]) {
++j; // If equal, update the value of j
}
pi[i] = j; // Update the prefix function value at the current position
}
// Return the computed Prefix Function
return pi;
}
// Example usage:
const s = "xyzxyzx";
const result = prefixFunction(s);
console.log("Prefix Function:", result.join(" "));
//This code is contributed by Utkarsh
Output
Prefix Function: 0 0 0 1 2 3 4
Find Prefix Function (Linear approach):
We can optimize the above approach to O(N). To compute , if , then , otherwise then we need to find the largest index j, such that and . Then we can compare characters at index j and i+1, if they are equal then , otherwise we need to find the next shortest j and repeat the procedure. If j becomes 0, then if , then will be 1 else 0.
For efficiently computing j, suppose we are currently at index i, we need to find the largest index j that holds the following condition: , this value is nothing but .
Below is the algorithm for the above approach:
- Create an array pi, which denotes the prefix function for string s. Initialize p[0] with 0.
- Run a loop from i=1 to n-1,
- Assign j to pi[i-1], j denotes the largest index which holds the following condition: .
- Compare s[j] and s[i], if they are equal assign p[i] will become j+1, else j will now become pi[j-1].
- Repeat the same procedure till j is greater than 0. If j becomes, s[0] and s[i] will get compared, if they are equal pi[i] will be 1 else 0.
- Return pi.
Below is the implementation of above approach:
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// Function to compute the optimized Prefix Function of a
// string in O(N) time
vector<int> prefix_function(string s)
{
int n = s.size();
// Create a vector to store the values of the Prefix
// Function
vector<int> pi(n);
// Iterate through the string starting from the second
// character
for (int i = 1; i < n; i++) {
// Initialize j with the value from the previous
// position
int j = pi[i - 1];
// Continue updating j until a match is found or j
// becomes 0
while (j > 0 && s[i] != s[j])
j = pi[j - 1];
// If a match is found, increment the length of the
// common prefix/suffix
if (s[i] == s[j])
j++;
// Update the Prefix Function value for the current
// position
pi[i] = j;
}
// Return the computed Prefix Function
return pi;
}
int main()
{
// Example usage
string text = "abababab";
vector<int> pf = prefix_function(text);
// Output the computed prefix function
cout << "Prefix Function values for string \"" << text
<< "\": ";
for (int i = 0; i < pf.size(); i++) {
cout << pf[i] << " ";
}
cout << endl;
return 0;
}
import java.util.*;
public class PrefixFunction {
// Function to compute the optimized Prefix Function of
// a string
public static List<Integer> prefixFunction(String s)
{
int n = s.length();
// Create an ArrayList to store the values of the
// Prefix Function
List<Integer> pi
= new ArrayList<>(Collections.nCopies(n, 0));
// Iterate through the string starting from the
// second character
for (int i = 1; i < n; i++) {
// Initialize j with the value from the previous
// position
int j = pi.get(i - 1);
// Continue updating j until a match is found or
// j becomes 0
while (j > 0 && s.charAt(i) != s.charAt(j))
j = pi.get(j - 1);
// If a match is found, increment the length of
// the common prefix/suffix
if (s.charAt(i) == s.charAt(j))
j++;
// Update the Prefix Function value for the
// current position
pi.set(i, j);
}
// Return the computed Prefix Function
return pi;
}
public static void main(String[] args)
{
// Example usage
String text = "abababab";
List<Integer> pf = prefixFunction(text);
// Output the computed prefix function
System.out.print(
"Prefix Function values for string \"" + text
+ "\": ");
for (int i = 0; i < pf.size(); i++) {
System.out.print(pf.get(i) + " ");
}
System.out.println();
}
}
def prefix_function(s):
n = len(s)
pi = [0] * n
for i in range(1, n):
j = pi[i - 1]
while j > 0 and s[i] != s[j]:
j = pi[j - 1]
if s[i] == s[j]:
j += 1
pi[i] = j
return pi
def main():
# Example usage
text = "abababab"
pf = prefix_function(text)
# Output the computed prefix function
print("Prefix Function values for string \"{}\": {}".format(
text, " ".join(map(str, pf))))
if __name__ == "__main__":
main()
function prefixFunction(s) {
const n = s.length;
// Create an array to store the values of the Prefix Function
const pi = new Array(n).fill(0);
// Iterate through the string starting from the second character
for (let i = 1; i < n; i++) {
// Initialize j with the value from the previous position
let j = pi[i - 1];
// Continue updating j until a match is found or j becomes 0
while (j > 0 && s.charAt(i) !== s.charAt(j)) {
j = pi[j - 1];
}
// If a match is found, increment the length of the common prefix/suffix
if (s.charAt(i) === s.charAt(j)) {
j++;
}
// Update the Prefix Function value for the current position
pi[i] = j;
}
// Return the computed Prefix Function
return pi;
}
function main() {
// Example usage
const text = "abababab";
const pf = prefixFunction(text);
// Output the computed prefix function
console.log(`Prefix Function values for string "${text}": ${pf.join(' ')}`);
}
main();
Output
Prefix Function values for string "abababab": 0 0 1 2 3 4 5 6
Use Cases of Prefix Function and KMP Algorithm in Competitive Programming:
1. Pattern Searching- The Knuth-Morris-Pratt algorithm:
Problem: Given a patter p and text t, the task is to find all occurrences of pattern p in text t.
The idea is to choose a character ($ or #) which is not present in any of the string p and t, which acts a separator. Compute the prefix function for the string p+#+t. Notice the value of prefix function at any index will not exceed n because of the separator. Now if , at any position i, that means a match is found, i.e., occurrence of patter p in text t. Notice the , won’t be true for first n+1 positions in prefix function since it belongs to pattern p and separator #. Hence we take all positions where .
Below is the implementation of above approach:
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class KMPAlgorithm {
public:
// Function to compute the optimized Prefix Function of a string in O(N) time
static vector<int> prefixFunction(const string& s) {
int n = s.size();
vector<int> pi(n);
for (int i = 1; i < n; i++) {
int j = pi[i - 1];
while (j > 0 && s[i] != s[j])
j = pi[j - 1];
if (s[i] == s[j])
j++;
pi[i] = j;
}
return pi;
}
// Function to find all occurrences of pattern p in text t using KMP algorithm
static vector<int> patternSearching(const string& t, const string& p) {
int n = p.size(), m = t.size();
string s = p + "#" + t;
vector<int> pi = prefixFunction(s);
vector<int> ans;
for (int i = n + 1; i < n + 1 + m; i++) {
if (pi[i] == n) {
ans.push_back(i - 2 * n);
}
}
return ans;
}
};
// Example usage
int main() {
string text = "ababcababcabc";
string pattern = "abc";
vector<int> occurrences = KMPAlgorithm::patternSearching(text, pattern);
cout << "Pattern occurrences: ";
for (int pos : occurrences) {
cout << pos << " ";
}
cout << endl;
return 0;
}
import java.util.ArrayList;
import java.util.List;
public class KMPAlgorithm {
// Function to compute the optimized Prefix Function of a string in O(N) time
public static int[] prefixFunction(String s) {
int n = s.length();
// Create an array to store the values of the Prefix Function
int[] pi = new int[n];
// Iterate through the string starting from the second character
for (int i = 1; i < n; i++) {
// Initialize j with the value from the previous position
int j = pi[i - 1];
// Continue updating j until a match is found or j becomes 0
while (j > 0 && s.charAt(i) != s.charAt(j))
j = pi[j - 1];
// If a match is found, increment the length of the common prefix/suffix
if (s.charAt(i) == s.charAt(j))
j++;
// Update the Prefix Function value for the current position
pi[i] = j;
}
// Return the computed Prefix Function
return pi;
}
// Function to find all occurrences of pattern p in text t using KMP algorithm
public static List<Integer> patternSearching(String t, String p) {
int n = p.length(), m = t.length();
// Combine pattern p, separator '#', and text t
String s = p + "#" + t;
// Compute the Prefix Function for the combined string
int[] pi = prefixFunction(s);
// List to store the positions where the pattern is found in the text
List<Integer> ans = new ArrayList<>();
// Iterate through the Prefix Function results to find pattern occurrences
for (int i = n + 1; i < n + 1 + m; i++) { // Adjust index based on combined string
if (pi[i] == n) {
ans.add(i - 2 * n); // Record the starting position of the pattern occurrence
}
}
// Return the positions where the pattern is found in the text
return ans;
}
public static void main(String[] args) {
String text = "ababcababcabc";
String pattern = "abc";
// Find all occurrences of pattern in the text using KMP algorithm
List<Integer> occurrences = patternSearching(text, pattern);
// Print the positions where the pattern is found
System.out.println("Pattern occurrences: " + occurrences);
}
}
def prefix_function(s):
"""
Function to compute the optimized Prefix Function of a string in O(N) time
Args:
s (str): The input string
Returns:
list: The Prefix Function values for the input string
"""
n = len(s)
pi = [0] * n # Create an array to store the values of the Prefix Function
# Iterate through the string starting from the second character
for i in range(1, n):
# Initialize j with the value from the previous position
j = pi[i - 1]
# Continue updating j until a match is found or j becomes 0
while j > 0 and s[i] != s[j]:
j = pi[j - 1]
# If a match is found, increment the length of the common prefix/suffix
if s[i] == s[j]:
j += 1
# Update the Prefix Function value for the current position
pi[i] = j
# Return the computed Prefix Function
return pi
def pattern_searching(t, p):
"""
Function to find all occurrences of pattern p in text t using KMP algorithm
Args:
t (str): The input text
p (str): The pattern to search for in the text
Returns:
list: Positions where the pattern is found in the text
"""
n, m = len(p), len(t)
# Combine pattern p, separator '#', and text t
s = p + '#' + t
# Compute the Prefix Function for the combined string
pi = prefix_function(s)
# List to store the positions where the pattern is found in the text
occurrences = []
# Iterate through the Prefix Function results to find pattern occurrences
for i in range(n + 1, n + m + 1):
if pi[i] == n:
# Record the starting position of the pattern occurrence
occurrences.append(i - 2 * n)
# Return the positions where the pattern is found in the text
return occurrences
text = "ababcababcabc"
pattern = "abc"
# Find all occurrences of pattern in the text using KMP algorithm
occurrences = pattern_searching(text, pattern)
# Print the positions where the pattern is found
print("Pattern occurrences:", occurrences)
class KMPAlgorithm {
// Function to compute the optimized Prefix Function of a string in O(N) time
static prefixFunction(s) {
let n = s.length;
// Create an array to store the values of the Prefix Function
let pi = new Array(n).fill(0);
// Iterate through the string starting from the second character
for (let i = 1; i < n; i++) {
// Initialize j with the value from the previous position
let j = pi[i - 1];
// Continue updating j until a match is found or j becomes 0
while (j > 0 && s[i] !== s[j]) {
j = pi[j - 1];
}
// If a match is found, increment the length of the common prefix/suffix
if (s[i] === s[j]) {
j++;
}
// Update the Prefix Function value for the current position
pi[i] = j;
}
// Return the computed Prefix Function
return pi;
}
// Function to find all occurrences of pattern p in text t using KMP algorithm
static patternSearching(t, p) {
let n = p.length, m = t.length;
// Combine pattern p, separator '#', and text t
let s = p + "#" + t;
// Compute the Prefix Function for the combined string
let pi = KMPAlgorithm.prefixFunction(s);
// Array to store the positions where the pattern is found in the text
let ans = [];
// Iterate through the Prefix Function results to find pattern occurrences
for (let i = n + 1; i < n + 1 + m; i++) {
if (pi[i] === n) {
ans.push(i - 2 * n); // Record the starting position of the pattern occurrence
}
}
// Return the positions where the pattern is found in the text
return ans;
}
}
// Example usage
let text = "ababcababcabc";
let pattern = "abc";
// Find all occurrences of pattern in the text using KMP algorithm
let occurrences = KMPAlgorithm.patternSearching(text, pattern);
// Print the positions where the pattern is found
console.log("Pattern occurrences: ", occurrences);
// This code is contributed by Rambabu
2. Count the number of occurrences of each prefix in same string:
Problem: Given a string s, find the number of occurrences of each prefix of string s in the same string i.e., string s.
The idea is to calculate the prefix function for the string s. Notice that each prefix appears at least 1 times, so we initialize the answer array with 1. Now denotes the length of longest prefix that occurs in s and ends at position i. The next shortest prefix of length j that occurs in s and ends at position i can be determined by and so on. To compute the final answer array efficiently, we count the number of number of times each value in prefix function appears. Then iterate from n-1 to 1 and for each value of increment the value at index of final answer array by .
Below is the implementation of above approach:
// Function to compute the optimized Prefix Function of a
// string in O(N) time
vector<int> prefix_function(string s) {
int n = s.size();
// Create a vector to store the values of the Prefix
// Function
vector<int> pi(n);
// Iterate through the string starting from the second
// character
for (int i = 1; i < n; i++) {
// Initialize j with the value from the previous
// position
int j = pi[i - 1];
// Continue updating j until a match is found or j
// becomes 0
while (j > 0 && s[i] != s[j])
j = pi[j - 1];
// If a match is found, increment the length of the
// common prefix/suffix
if (s[i] == s[j])
j++;
// Update the Prefix Function value for the current
// position
pi[i] = j;
}
// Return the computed Prefix Function
return pi;
}
// Function to count the number of occurrences of each
// prefix in the same string
vector<int> prefix_occurrence(string s) {
int n = s.size();
// Compute the Prefix Function
vector<int> pi = prefix_function(s), count(n + 1, 0);
// Count the occurrences of each value in the Prefix Function
for (int i = 0; i < n; i++)
count[pi[i]]++;
// Iterate from n-1 to 1 and update the count array
for (int i = n - 1; i > 0; i--)
count[pi[i - 1]] += count[i];
// Increment the count array for each prefix
for (int i = 1; i <= n; i++)
count[i]++;
return count;
}
import java.util.*;
public class PrefixFunction {
// Function to compute the optimized Prefix Function of
// a string in O(N) time
static int[] prefixFunction(String s)
{
int n = s.length();
// Create an array to store the values of the Prefix
// Function
int[] pi = new int[n];
// Iterate through the string starting from the
// second character
for (int i = 1; i < n; i++) {
// Initialize j with the value from the previous
// position
int j = pi[i - 1];
// Continue updating j until a match is found or
// j becomes 0
while (j > 0 && s.charAt(i) != s.charAt(j))
j = pi[j - 1];
// If a match is found, increment the length of
// the common prefix/suffix
if (s.charAt(i) == s.charAt(j))
j++;
// Update the Prefix Function value for the
// current position
pi[i] = j;
}
// Return the computed Prefix Function
return pi;
}
// Function to count the number of occurrences of each
// prefix in the same string
static int[] prefixOccurrence(String s)
{
int n = s.length();
// Compute the Prefix Function
int[] pi = prefixFunction(s);
int[] count = new int[n + 1];
// Count the occurrences of each value in the Prefix
// Function
for (int i = 0; i < n; i++)
count[pi[i]]++;
// Iterate from n-1 to 1 and update the count array
for (int i = n - 1; i > 0; i--)
count[pi[i - 1]] += count[i];
// Increment the count array for each prefix
for (int i = 1; i <= n; i++)
count[i]++;
return count;
}
// Main method to test the functions
public static void main(String[] args)
{
String s = "abababa";
int[] prefix = prefixFunction(s);
int[] occurrence = prefixOccurrence(s);
System.out.println("Prefix Function:");
System.out.println(Arrays.toString(prefix));
System.out.println("Prefix Occurrence:");
System.out.println(Arrays.toString(occurrence));
}
}
// This code is contributed by Rambabu
3. Count the number of occurrences of each prefix in some other string:
Problem: Given a string s, find the number of occurrences of each prefix of string s in the string t.
The idea is to compute the prefix function of the string s#t. Notice that we only care about the value , where i>n since we need to find number of occurrences of s in t, and t begins from index n+1, where n is the length of string s. Now we can repeat the same procedure as we did in counting the number of occurrences of each prefix in same string.
Below is the implementation of above approach:
#include <bits/stdc++.h>
using namespace std;
// Function to compute the optimized Prefix Function of a
// string in O(N) time
vector<int> prefix_function(string s)
{
int n = s.size();
// Create a vector to store the values of the Prefix
// Function
vector<int> pi(n);
// Iterate through the string starting from the second
// character
for (int i = 1; i < n; i++) {
// Initialize j with the value from the previous
// position
int j = pi[i - 1];
// Continue updating j until a match is found or j
// becomes 0
while (j > 0 && s[i] != s[j])
j = pi[j - 1];
// If a match is found, increment the length of the
// common prefix/suffix
if (s[i] == s[j])
j++;
// Update the Prefix Function value for the current
// position
pi[i] = j;
}
// Return the computed Prefix Function
return pi;
}
// Function to count the number of occurrences of each
// prefix of string s in a different string t
vector<int> prefix_occurrence(string s, string t)
{
int n = s.size();
int m = t.size();
// Combine strings s and t with a separator '#'
string combined_string = s + "#" + t;
// Compute the Prefix Function for the combined string
vector<int> pi = prefix_function(combined_string),
count(n + 1, 0);
// Count the occurrences of each value in the Prefix
// Function
for (int i = n + 1; i <= n + m; i++)
count[pi[i]]++;
// Iterate from n-1 to 1 and update the count array
for (int i = n - 1; i > 0; i--)
count[pi[i - 1]] += count[i];
// Increment the count array for each prefix
for (int i = 1; i <= n; i++)
count[i]++;
return count;
}
// Main function with example
int main()
{
// Example
string s = "aba";
string t = "abacaba";
vector<int> occurrences = prefix_occurrence(s, t);
cout << "Occurrences of prefixes of \"" << s
<< "\" in \"" << t << "\": ";
for (int occ : occurrences) {
cout << occ << " ";
}
cout << endl;
return 0;
}
import java.util.*;
public class PrefixFunction {
// Function to compute the optimized Prefix Function of
// a string in O(N) time
static List<Integer> prefixFunction(String s)
{
int n = s.length();
// Create a list to store the values of the Prefix
// Function
List<Integer> pi = new ArrayList<>(n);
// Initialize the first element of pi with 0
pi.add(0);
// Iterate through the string starting from the
// second character
for (int i = 1; i < n; i++) {
// Initialize j with the value from the previous
// position
int j = pi.get(i - 1);
// Continue updating j until a match is found or
// j becomes 0
while (j > 0 && s.charAt(i) != s.charAt(j))
j = pi.get(j - 1);
// If a match is found, increment the length of
// the common prefix/suffix
if (s.charAt(i) == s.charAt(j))
j++;
// Update the Prefix Function value for the
// current position
pi.add(j);
}
// Return the computed Prefix Function
return pi;
}
// Function to count the number of occurrences of each
// prefix of string s in a different string t
static List<Integer> prefixOccurrence(String s,
String t)
{
int n = s.length();
int m = t.length();
// Combine strings s and t with a separator '#'
String combinedString = s + "#" + t;
// Compute the Prefix Function for the combined
// string
List<Integer> pi = prefixFunction(combinedString);
List<Integer> count = new ArrayList<>(
Collections.nCopies(n + 1, 0));
// Count the occurrences of each value in the Prefix
// Function
for (int i = n + 1; i <= n + m; i++)
count.set(pi.get(i), count.get(pi.get(i)) + 1);
// Iterate from n-1 to 1 and update the count list
for (int i = n - 1; i > 0; i--)
count.set(pi.get(i - 1),
count.get(pi.get(i - 1))
+ count.get(i));
// Increment the count list for each prefix
for (int i = 1; i <= n; i++)
count.set(i, count.get(i) + 1);
return count;
}
// Main method with example
public static void main(String[] args)
{
// Example
String s = "aba";
String t = "abacaba";
List<Integer> occurrences = prefixOccurrence(s, t);
System.out.println("Occurrences of prefixes of \""
+ s + "\" in \"" + t
+ "\": " + occurrences);
}
}
def prefix_function(s):
n = len(s)
pi = [0] * n
for i in range(1, n):
j = pi[i - 1]
while j > 0 and s[i] != s[j]:
j = pi[j - 1]
if s[i] == s[j]:
j += 1
pi[i] = j
return pi
def prefix_occurrence(s, t):
n = len(s)
m = len(t)
combined_string = s + '#' + t
pi = prefix_function(combined_string)
count = [0] * (n + 1)
for i in range(n + 1, n + m + 1):
count[pi[i]] += 1
for i in range(n - 1, 0, -1):
count[pi[i - 1]] += count[i]
for i in range(1, n + 1):
count[i] += 1
return count
# Main method with example
if __name__ == "__main__":
s = "aba"
t = "abacaba"
occurrences = prefix_occurrence(s, t)
print(f'Occurrences of prefixes of "{s}" in "{t}": {occurrences}')
// Function to compute the optimized Prefix Function of a
// string in O(N) time
function prefixFunction(s) {
const n = s.length;
// Create an array to store the values of the Prefix Function
const pi = new Array(n).fill(0);
// Iterate through the string starting from the second character
for (let i = 1; i < n; i++) {
// Initialize j with the value from the previous position
let j = pi[i - 1];
// Continue updating j until a match is found or j becomes 0
while (j > 0 && s[i] !== s[j])
j = pi[j - 1];
// If a match is found, increment the length of the common prefix/suffix
if (s[i] === s[j])
j++;
// Update the Prefix Function value for the current position
pi[i] = j;
}
// Return the computed Prefix Function
return pi;
}
// Function to count the number of occurrences of each
// prefix of string s in a different string t
function prefixOccurrence(s, t) {
const n = s.length;
const m = t.length;
// Combine strings s and t with a separator '#'
const combinedString = s + "#" + t;
// Compute the Prefix Function for the combined string
const pi = prefixFunction(combinedString);
const count = new Array(n + 1).fill(0);
// Count the occurrences of each value in the Prefix Function
for (let i = n + 1; i <= n + m; i++)
count[pi[i]]++;
// Iterate from n-1 to 1 and update the count array
for (let i = n - 1; i > 0; i--)
count[pi[i - 1]] += count[i];
// Increment the count array for each prefix
for (let i = 1; i <= n; i++)
count[i]++;
return count;
}
// Main function with example
function main() {
// Example
const s = "aba";
const t = "abacaba";
const occurrences = prefixOccurrence(s, t);
process.stdout.write("Occurrences of prefixes of \"" + s + "\" in \"" + t + "\": ");
for (const occ of occurrences) {
process.stdout.write(occ + " ");
}
process.stdout.write("\n");
}
// Run main function
main();
//This code is contribited by Prachi.
Output
Occurrences of prefixes of "aba" in "abacaba": 5 3 3 3
4. Count the number of occurrences of each prefix in same string that also occurs as the suffix:
Problem: Given a string s, find the number of occurrences of each prefix of string s in the string s which also occurs as the suffix of string s.
The idea is the compute the prefix function of string s. To find the number of occurrence of each prefix in sting s we can repeat the same procedure as done above. Now to find the lengths of prefix which also appears as suffix in string s,are- , ,… and so on. The number of times each of these prefixes occurs in string s can be directly determined as we pre computed the array which finds the number of occurrence of each prefix of string s in sting s.
Below is the implementation of above approach:
#include <bits/stdc++.h>
using namespace std;
// Function to compute the optimized Prefix Function of a
// string in O(N) time
vector<int> prefix_function(string s)
{
int n = s.size();
// Create a vector to store the values of the Prefix
// Function
vector<int> pi(n);
// Iterate through the string starting from the second
// character
for (int i = 1; i < n; i++) {
// Initialize j with the value from the previous
// position
int j = pi[i - 1];
// Continue updating j until a match is found or j
// becomes 0
while (j > 0 && s[i] != s[j])
j = pi[j - 1];
// If a match is found, increment the length of the
// common prefix/suffix
if (s[i] == s[j])
j++;
// Update the Prefix Function value for the current
// position
pi[i] = j;
}
// Return the computed Prefix Function
return pi;
}
// Function to count the number of occurrences of each
// prefix of string s in the same string s that also occurs
// as the suffix of s
void prefix_occurrence_with_suffix(string s)
{
int n = s.size();
// Compute the Prefix Function
vector<int> pi = prefix_function(s), count(n + 1, 0);
// Count the occurrences of each value in the Prefix
// Function
for (int i = 0; i < n; i++)
count[pi[i]]++;
// Iterate from n-1 to 1 and update the count array
for (int i = n - 1; i > 0; i--)
count[pi[i - 1]] += count[i];
for (int i = 1; i <= n; i++) {
count[i]++;
}
// Print the lengths and occurrences of prefixes that
// also occur as suffixes
int j = pi[n - 1];
while (j > 0) {
cout << "Length: " << j
<< ", Occurrences: " << count[j] << "\n";
j = pi[j - 1];
}
}
int main()
{
string s = "ABACABA";
prefix_occurrence_with_suffix(s);
return 0;
}
// Java program for the above approach
import java.util.*;
public class GFG {
// Function to compute the optimized Prefix Function of
// a string in O(N) time
static List<Integer> prefix_function(String s)
{
int n = s.length();
List<Integer> pi
= new ArrayList<>(Collections.nCopies(n, 0));
// Iterate through the string starting from the
// second character
for (int i = 1; i < n; i++) {
// Initialize j with the value from the previous
// position
int j = pi.get(i - 1);
// Continue updating j until a match is found or
// j becomes 0
while (j > 0 && s.charAt(i) != s.charAt(j))
j = pi.get(j - 1);
// If a match is found, increment the length of
// the common prefix/suffix
if (s.charAt(i) == s.charAt(j))
j++;
// Update the Prefix Function value for the
// current position
pi.set(i, j);
}
// Return the computed Prefix Function
return pi;
}
// Function to count the number of occurrences of each
// prefix of string s in the same string s that also
// occurs as the suffix of s
static void prefix_occurrence_with_suffix(String s)
{
int n = s.length();
// Compute the Prefix Function
List<Integer> pi = prefix_function(s);
int[] count = new int[n + 1];
// Count the occurrences of each value in the Prefix
// Function
for (int i = 0; i < n; i++)
count[pi.get(i)]++;
// Iterate from n-1 to 1 and update the count array
for (int i = n - 1; i > 0; i--)
count[pi.get(i - 1)] += count[i];
for (int i = 1; i <= n; i++)
count[i]++;
// Print the lengths and occurrences of prefixes
// that also occur as suffixes
int j = pi.get(n - 1);
while (j > 0) {
System.out.println("Length: " + j
+ ", Occurrences: "
+ count[j]);
j = pi.get(j - 1);
}
}
public static void main(String[] args)
{
String s = "ABACABA";
prefix_occurrence_with_suffix(s);
}
}
// This code is contributed by Susobhan Akhuli
def prefix_function(s):
n = len(s)
pi = [0] * n
for i in range(1, n):
j = pi[i - 1]
while j > 0 and s[i] != s[j]:
j = pi[j - 1]
if s[i] == s[j]:
j += 1
pi[i] = j
return pi
def prefix_occurrence_with_suffix(s):
n = len(s)
pi = prefix_function(s)
count = [0] * (n + 1)
for i in range(n):
count[pi[i]] += 1
for i in range(n - 1, 0, -1):
count[pi[i - 1]] += count[i]
for i in range(1, n + 1):
count[i] += 1
j = pi[n - 1]
while j > 0:
print(f'Length: {j}, Occurrences: {count[j]}')
j = pi[j - 1]
if __name__ == "__main__":
s = "ABACABA"
prefix_occurrence_with_suffix(s)
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG {
// Function to compute the optimized Prefix Function of
// a string in O(N) time
static List<int> PrefixFunction(string s)
{
int n = s.Length;
// Create a list to store the values of the Prefix
// Function
List<int> pi = new List<int>();
// Initialize the first element of the Prefix
// Function
pi.Add(0);
// Iterate through the string starting from the
// second character
for (int i = 1; i < n; i++) {
// Initialize j with the value from the previous
// position
int j = pi[i - 1];
// Continue updating j until a match is found or
// j becomes 0
while (j > 0 && s[i] != s[j])
j = pi[j - 1];
// If a match is found, increment the length of
// the common prefix/suffix
if (s[i] == s[j])
j++;
// Update the Prefix Function value for the
// current position
pi.Add(j);
}
// Return the computed Prefix Function
return pi;
}
// Function to count the number of occurrences of each
// prefix of string s in the same string s that also
// occurs as the suffix of s
static void PrefixOccurrenceWithSuffix(string s)
{
int n = s.Length;
// Compute the Prefix Function
List<int> pi = PrefixFunction(s);
int[] count = new int[n + 1];
// Count the occurrences of each value in the Prefix
// Function
for (int i = 0; i < n; i++)
count[pi[i]]++;
// Iterate from n-1 to 1 and update the count array
for (int i = n - 1; i > 0; i--)
count[pi[i - 1]] += count[i];
for (int i = 1; i <= n; i++)
count[i]++;
// Print the lengths and occurrences of prefixes
// that also occur as suffixes
int j = pi[n - 1];
while (j > 0) {
Console.WriteLine("Length: " + j
+ ", Occurrences: "
+ count[j]);
j = pi[j - 1];
}
}
static void Main(string[] args)
{
string s = "ABACABA";
PrefixOccurrenceWithSuffix(s);
}
}
// This code is contributed by Susobhan Akhuli
// Function to compute the optimized Prefix Function of a string in O(N) time
function prefix_function(s) {
const n = s.length;
// Create an array to store the values of the Prefix Function
const pi = new Array(n).fill(0);
// Iterate through the string starting from the second character
for (let i = 1; i < n; i++) {
// Initialize j with the value from the previous position
let j = pi[i - 1];
// Continue updating j until a match is found or j becomes 0
while (j > 0 && s[i] !== s[j])
j = pi[j - 1];
// If a match is found, increment the length of the common prefix/suffix
if (s[i] === s[j])
j++;
// Update the Prefix Function value for the current position
pi[i] = j;
}
// Return the computed Prefix Function
return pi;
}
// Function to count the number of occurrences of each prefix of string s
// in the same string s that also occurs as the suffix of s
function prefix_occurrence_with_suffix(s) {
const n = s.length;
// Compute the Prefix Function
const pi = prefix_function(s);
const count = new Array(n + 1).fill(0);
// Count the occurrences of each value in the Prefix Function
for (let i = 0; i < n; i++)
count[pi[i]]++;
// Iterate from n-1 to 1 and update the count array
for (let i = n - 1; i > 0; i--)
count[pi[i - 1]] += count[i];
for (let i = 1; i <= n; i++) {
count[i]++;
}
// Print the lengths and occurrences of prefixes that also occur as suffixes
let j = pi[n - 1];
while (j > 0) {
console.log("Length:", j, ", Occurrences:", count[j]);
j = pi[j - 1];
}
}
// Main function
function main() {
const s = "ABACABA";
prefix_occurrence_with_suffix(s);
}
// Call the main function
main();
Output
Length: 3, Occurrences: 2 Length: 1, Occurrences: 4
Practice Problems of KMP Algorithm for Competitive Programming:
Problem | Problem Link |
|---|---|
Minimum characters to be added at front to make string palindrome | Practice |
Minimum size substring to be removed to make a given string palindromic | Practice |
Maximum number of given operations to remove the entire string | Practice |
Contact Us