JetBrains Academy: Knuth Morris Pratt algorithm in Java - Kamil-Jankowski/Learning-JAVA GitHub Wiki
Non-overlapping occurrences of a pattern:
Write a program that finds all non-overlapping occurrences of a pattern in a text.
Input: two strings, a pattern p and a text t.
Output: the first line should contain the number of non-overlapping occurrences of the pattern in the text. The second line should contain the index of these occurrences separated by space.
For two overlapping substrings, consider as occurrence the one that has the least starting index (it is supposed that a searching starts from the beginning of the text).
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String pattern = scanner.nextLine();
String text = scanner.nextLine();
List<Integer> kmpNonOverlap = KMP.kmpNonOverlapping(pattern, text);
System.out.println(kmpNonOverlap.size());
kmpNonOverlap.forEach(e -> System.out.print(e + " "));
}
}
class KMP {
public static int[] prefixFunction(String str) {
int[] prefixFunc = new int[str.length()];
for (int i = 1; i < str.length(); i++) {
int j = prefixFunc[i - 1];
while (j > 0 && str.charAt(i) != str.charAt(j)) {
j = prefixFunc[j - 1];
}
if (str.charAt(i) == str.charAt(j)) {
j += 1;
}
prefixFunc[i] = j;
}
return prefixFunc;
}
public static List<Integer> kmpNonOverlapping(String pattern, String text) {
int[] prefixFunc = prefixFunction(pattern);
ArrayList<Integer> occurrences = new ArrayList<>();
int j = 0;
for (int i = 0; i < text.length(); i++) {
while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
j = prefixFunc[j - 1];
}
if (text.charAt(i) == pattern.charAt(j)) {
j += 1;
}
if (j == pattern.length()) {
occurrences.add(i - j + 1);
j = prefixFunc[0]; // modified not to take into account any previous matches
}
}
return occurrences;
}
}Number of distinct substrings in a string:
Given a string s. Write a program that counts the number of distinct substrings contained in s.
NB: Remember about the empty string.
Hint: Suppose we already know the number of distinct substrings for s[(i+1):∣s∣]. Now let's add a symbol s[i] to the beginning of this substring. Thus, we add s[i:|s|] new substrings. But how many of them did not appear before?
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String text = scanner.nextLine();
int numberOfDistinctSubstrings = KMP.kmpDistinct(text);
System.out.println(numberOfDistinctSubstrings);
}
}
class KMP {
public static int[] prefixFunction(String str) {
int[] prefixFunc = new int[str.length()];
for (int i = 1; i < str.length(); i++) {
int j = prefixFunc[i - 1];
while (j > 0 && str.charAt(i) != str.charAt(j)) {
j = prefixFunc[j - 1];
}
if (str.charAt(i) == str.charAt(j)) {
j += 1;
}
prefixFunc[i] = j;
}
return prefixFunc;
}
public static int kmpDistinct(String text) {
int occurrences = 1;
if (text.length() >= 1) occurrences = 2;
for (int i = 1; i < text.length(); i++) {
String s = text.substring(0, i);
String t = text.substring(0, i + 1);
StringBuilder st = new StringBuilder(t);
String reversed = st.reverse().toString();
int[] prefixFunc = prefixFunction(reversed);
int maxP = maxPrefix(prefixFunc);
int newDistinctSubstrings = s.length() + 1 - maxP;
occurrences += newDistinctSubstrings;
}
return occurrences;
}
private static int maxPrefix(int[] prefixFunc) {
int max = Integer.MIN_VALUE;
for (int number : prefixFunc) {
if (number > max) {
max = number;
}
}
return max;
}
}Finding substrings in a matrix:
Given two matrices: a pattern pp and a text t. Write a program that counts the number of occurrences of p in t.
Input: the first line contains two numbers x and y — the number of rows and columns in a pattern. Each of the next x lines contains a string of length y. The following lines contain a text in the same format. It is guaranteed that the sizes of rows and columns both for the pattern and for the text are not equal to zero.
Output: the number of occurrences of the pattern in the text.
TBD