Интересно, как не учитывать повторные перестановки при рассмотрении строк внутри более длинных строк. На данный момент мне удалось создать программу, которая принимает строку, подвергает ее различным перестановкам и подсчитывает, сколько из них присутствует в более длинной строке, однако, что касается нахождения различий, я совершенно застрял; Любой совет будет высоко ценится!
import java.util.Scanner;
public class main {
static final int MAX = 200000;
public static int numbo;
public static void main (String args[]) {
new main ();
}
public main () {
String txt = "abacabaa";
String pat = "aab";
search(pat, txt);
System.out.println(numbo);
}
static boolean compare(char arr1[], char arr2[]) {
for (int i = 0; i < MAX; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
static void search(String pat, String txt) {
int M = pat.length();
int N = txt.length();
char[] countP = new char[MAX];
char[] countTW = new char[MAX];
for (int i = 0; i < M; i++) {
(countP[pat.charAt(i)])++;
(countTW[txt.charAt(i)])++;
}
//Goes through remaining characters of pattern
for (int i = M; i < N; i++) {
//Compares counts of current window of text with counts of pattern[]
if (compare(countP, countTW)) {
System.out.println("Found at Index " + (i - M));
numbo++;
}
//Adds current character to current window
(countTW[txt.charAt(i)])++;
//Removes the first character of previous window
countTW[txt.charAt(i-M)]--;
}
if (compare(countP, countTW)) {
numbo++;
System.out.println("Found at Index " + (N - M));
}
}
}