Это, пожалуй, не самое эффективное решение алгоритмически, но оно чистое с точки зрения дизайна класса. Это решение использует подход сравнения «отсортированных» данных слов.
Можно сказать, что слово является перестановкой другого, если оно содержит одни и те же буквы в одном и том же числе. Это означает, что вы можете преобразовать слово из String в Map<Character,Integer>. Такое преобразование будет иметь сложность O (n), где n - длина String, при условии, что вложения в вашу стоимость реализации Map O (1).
Map будет содержать в качестве ключей все символы, найденные в слове, а также значения частот символов.
Пример. Аббв преобразуется в [a->1, b->2, c->1]
bacb преобразуется в [a->1, b->2, c->1]
Так что, если вы должны знать, если два слова одна перестановка с другой стороны, вы можете конвертировать их обоих в карты, а затем вызвать Map.equals ,
Затем вам нужно перебрать текстовую строку и применить преобразование ко всем подстрокам одинаковой длины слов, которые вы ищете.
Улучшение предложенного Inerdial
Этого подход может быть улучшено путем обновления карты в моде «прокатки».
I.e. если вы соответствуете индексу i=3 в примере стога сена в OP (подстрока xya), то карта будет [a->1, x->1, y->1]. Когда вы продвигаетесь в стоге сена, уменьшите количество символов на haystack[i] и увеличите счетчик на haystack[i+needle.length()].
(Отбрасывание нулей, чтобы убедиться, что Map.equals() работы, или просто реализации пользовательских сравнения.)
Улучшения предложенного Макс
Что делать, если мы также ввести matchedCharactersCnt переменные? В начале стога сена будет 0. Каждый раз, когда вы меняете карту на нужное значение, вы увеличиваете переменную. Каждый раз, когда вы меняете его на желаемое значение, вы уменьшаете переменную. На каждой итерации вы проверяете, равна ли переменная длине иглы. Если это так - вы нашли совпадение. Это будет быстрее, чем сравнение полной карты каждый раз.
псевдокод обеспечивает Макс:
needle = "abbc"
text = "abbcbbabbcaabbca"
needleSize = needle.length()
//Map of needle character counts
targetMap = [a->1, b->2, c->1]
matchedLength = 0
curMap = [a->0, b->0, c->0]
//Initial map initialization
for (int i=0;i<needle.length();i++) {
if (curMap.contains(haystack[i])) {
matchedLength++
curMap[haystack[i]]++
}
}
if (matchedLength == needleSize) {
System.out.println("Match found at: 0");
}
//Search itself
for (int i=0;i<haystack.length()-needle.length();i++) {
int targetValue1 = targetMap[haystack[i]]; //Reading from hashmap, O(1)
int curValue1 = curMap[haystack[i]]; //Another read
//If we are removing beneficial character
if (targetValue1 > 0 && curValue1 > 0 && curValue1 <= targetValue1) {
matchedLength--;
}
curMap[haystack[i]] = curValue1 + 1; //Write to hashmap, O(1)
int targetValue2 = targetMap[haystack[i+needle.length()]] //Read
int curValue2 = curMap[haystack[i+needle.length()]] //Read
//We are adding a beneficial character
if (targetValue2 > 0 && curValue2 < targetValue2) { //If we don't need this letter at all, the amount of matched letters decreases
matchedLength++;
}
curMap[haystack[i+needle.length()]] = curValue2 + 1; //Write
if (matchedLength == needleSize) {
System.out.println("Match found at: "+(i+1));
}
}
//Basically with 4 reads and 2 writes which are
//independent of the size of the needle,
//we get to the maximal possible performance: O(n)
этого ответ кажется неполным. Вы говорите, как вы собираетесь канонизировать слово, но не говорите ничего о поиске перестановок в тексте. Вы бы использовали ту же идею, что и плакаты? –
В сочетании с второй идеей OP этот подход можно улучшить, обновив карту в режиме «прокатки». То есть если вы соответствуете индексу 'i = 3' в примере haystack в OP (подстрока' xya'), карта будет '[a-> 1, x-> 1, y-> 1]'. Когда вы продвигаетесь в стоге сена, уменьшите количество символов для 'haystack [i]' и увеличьте количество для 'haystack [i + needle.length()]'. (Отбрасывание нулей, чтобы убедиться, что 'Map.equals()' работает или просто реализует пользовательское сравнение.) – millimoose
@Inerdial ваше улучшение действительно элегантно! Congrats !! –