public class OverlappingSubstringCountOptimized {
public static void main(String[] args) {
String input = "ababababa";
String substringToCount = "aba";
int count = countSubstringOccurrences(input, substringToCount);
System.out.println("The overlapping substring appears " + count + " times.");
}
static int countSubstringOccurrences(String text, String pattern) {
int n = text.length();
int m = pattern.length();
int[] lps = computeLPSArray(pattern);
int count = 0;
int i = 0;
int j = 0;
while (i < n) {
if (pattern.charAt(j) == text.charAt(i)) {
i++;
j++;
}
if (j == m) {
count++;
j = lps[j - 1];
}
else if (i < n && pattern.charAt(j) != text.charAt(i)) {
if (j != 0) {
j = lps[j - 1];
} else {
i++;
}
}
}
return count;
}
static int[] computeLPSArray(String pattern) {
int length = 0;
int i = 1;
int m = pattern.length();
int[] lps = new int[m];
while (i < m) {
if (pattern.charAt(i) == pattern.charAt(length)) {
length++;
lps[i] = length;
i++;
} else {
if (length != 0) {
length = lps[length - 1];
} else {
lps[i] = 0;
i++;
}
}
}
return lps;
}
}