Как найти все перестановки данного слова в заданном тексте?

Это, пожалуй, не самое эффективное решение алгоритмически, но оно чистое с точки зрения дизайна classа. Это решение использует подход сравнения «отсортированных» данных слов.

Мы можем сказать, что слово является перестановкой другого, если оно содержит одни и те же буквы в одном и том же числе. Это означает, что вы можете преобразовать слово из String в Map . Такое преобразование будет иметь сложность O (n), где n – длина String , предполагая, что вставки в вашей реализации реализации Map O (1).

Map будет содержать в качестве ключей все символы, найденные в слове, а также значения частот символов.

Пример . abbc преобразуется в [a->1, b->2, c->1]

bacb преобразуется в [a->1, b->2, c->1]

Поэтому, если вам нужно знать, являются ли два слова одной из перестановок другой, вы можете преобразовать их в карты и затем вызвать Map.equals .

Затем вам нужно перебрать текстовую строку и применить преобразование ко всем подстрокам той же длины слов, которые вы ищете.

Улучшение, предлагаемое Inerdial

Этот подход можно улучшить, обновив карту в режиме «прокатки».

Т.е. если вы сопоставляете индекс i=3 в примере haystack в OP (подстрока xya ), то карта будет [a->1, x->1, y->1] . Когда вы продвигаетесь в стоге сена, уменьшите количество символов для haystack[i] и haystack[i+needle.length()] счетчик для haystack[i+needle.length()] .

(Отбрасывание нhive, чтобы убедиться, что Map.equals() работает или просто реализует пользовательское сравнение.)

Улучшение, предложенное Max

Что делать, если мы также matchedCharactersCnt переменную matchedCharactersCnt ? В начале стога сена будет 0 . Каждый раз, когда вы меняете карту на нужное значение, вы увеличиваете переменную. Каждый раз, когда вы меняете его на желаемое значение, вы уменьшаете переменную. На каждой итерации вы проверяете, равна ли переменная длине иглы. Если это так – вы нашли совпадение. Это будет быстрее, чем сравнение полной карты каждый раз.

Псевдокод, предоставленный Max:

 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 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) 

Чтобы найти перестановку строки, вы можете использовать теорию чисел. Но вам придется знать «теорию» за этим алгоритмом заранее, прежде чем вы сможете ответить на вопрос, используя этот алгоритм.

Существует метод, в котором вы можете вычислить hash строки с использованием простых чисел. Каждая перестановка одной и той же строки даст одно и то же значение hash-функции. Вся другая комбинация строк, которая не является перестановкой, даст некоторое другое значение hash-функции.

Хеш-значение вычисляется с помощью c ₁ * p ₁ + c ₂ * p ₂ + … + c _n * p _n, где c _i – единственное значение для текущего символа в строке и где p _i – единственное правое числовое значение для c _i char.

Вот реализация.

 public class Main { static int[] primes = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103 }; public static void main(String[] args) { final char[] text = "abcxaaabbbccyaxbcayaaaxycab" .toCharArray(); char[] abc = new char[]{'a','b','c'}; int match = val(abc); for (int i = 0; i < text.length - 2; i++) { char[] _123 = new char[]{text[i],text[i+1],text[i+2]}; if(val(_123)==match){ System.out.println(new String(_123) ); } } } static int p(char c) { return primes[(int)c - (int)'a']; } static int val(char[] cs) { return p(cs[0])*(int)cs[0] + p(cs[1])*(int)cs[1] + p(cs[2])*(int)cs[2]; } } 

Выходной сигнал: abc bca cab

Вы должны сделать это за один проход. Начните с создания карты, содержащей все символы слова, которое вы ищете. Поэтому изначально карта содержит [a, b, c] .

Теперь пройдите текст по одному символу за раз. Цикл выглядит примерно так, в псевдокоде.

 found_string = ""; for each character in text if character is in map remove character from map append character to found_string if map is empty output found_string found_string = "" add all characters back to map end if else // not a permutation of the string you're searching for refresh map with characters from found_string found_string = "" end if end for 

Если вы хотите уникальные вхождения, измените шаг вывода так, чтобы он добавлял найденные строки к карте. Это устранит дубликаты.

Есть вопрос о словах, которые содержат дублированные письма. Если это проблема, сделайте ключ буквой, а значение – счетчиком. «Удаление» символа означает уменьшение его количества на карте. Если счетчик переходит в 0, тогда символ фактически удаляется с карты.

Алгоритм, как написано, не найдет перекрывающиеся вхождения. То есть, учитывая текст abcba , он найдет только abc . Если вы хотите обрабатывать перекрывающиеся вхождения, вы можете изменить алгоритм так, чтобы, когда он находит совпадение, он уменьшает индекс на единицу за вычетом длины найденной строки.

Это была забавная головоломка. Благодарю.

Это то, что я хотел бы сделать – настроить массив флагов с одним элементом, равным 0 или 1, чтобы указать, был ли этот символ в STR сопоставлен

Установите первый результат в RESULT на пустой.

для каждого символа C в тексте:

Установите массив X равным длине STR ко всем нулям.

для каждого символа S в STR: если C является символом JTH в STR и X [J] == 0, тогда установите X [J] <= 1 и добавьте C в RESULT. Если длина RESULT равна STR, добавьте RESULT в список перестановок и снова установите элементы X [] в ноль.

Если C не является символом J в STR с X [J] == 0, то снова установите элементы X [] в нули.

Второй подход кажется мне очень изящным и должен быть вполне приемлемым. Я думаю, что он масштабируется в O(M * N log N) , где N – длина слова, а M – длина текста.

Я могу придумать несколько более сложный алгоритм O(M) :

1. Подсчитайте появление каждого символа в слове
2. Сделайте то же самое для первых символов N (т.е. length(word) ) текста
3. Вычтите два частотных вектора, получив subFreq
4. Подсчитайте количество ненулевых subFreq в subFreq , получив numDiff
5. Если numDiff равно нулю, существует совпадение
6. Обновлять subFreq и numDiff в постоянное время путем обновления для первого и последующего символов в тексте
7. Перейдите к 5, пока не дойдете до конца текста.

EDIT : Посмотрите, что было опубликовано несколько похожих ответов. Большая часть этого алгоритма эквивалентна подсчету частоты вращения, предложенной другими. Мое скромное дополнение также обновляет количество различий в прокатной моде, что дает алгоритм O(M+N) , а не O(M*N) .

EDIT2 : Только что увидел, что Макс в основном предложил это в комментариях, так что коричневое указывает на него.

Этот код должен выполнять работу:

 import java.util.ArrayList; import java.util.List; public class Permutations { public static void main(String[] args) { final String word = "abc"; final String text = "abcxaaabbbccyaxbcayxycab"; List charsActuallyFound = new ArrayList(); StringBuilder match = new StringBuilder(3); for (Character c : text.toCharArray()) { if (word.contains(c.toString()) && !charsActuallyFound.contains(c)) { charsActuallyFound.add(c); match.append(c); if (match.length()==word.length()) { System.out.println(match); match = new StringBuilder(3); charsActuallyFound.clear(); } } else { match = new StringBuilder(3); charsActuallyFound.clear(); } } } } 

Список charsActuallyFound используется для отслеживания символа, уже найденного в цикле. Необходимо избегать математического «aaa» «bbb» «ccc» (добавленный мной к указанному вами тексту).

После дальнейшего размышления, я думаю, что мой код работает только в том случае, если данное слово не имеет повторяющихся символов. Правильный код выше

 abc bca cab 

но если вы морфинг для слова «aaa», тогда ничего не печатается, потому что каждый символ не может быть сопоставлен более одного раза. Вдохновленный от Джима Mischel ответ, я редактирую свой код, заканчивая этим:

 import java.util.ArrayList; import java.util.List; public class Permutations { public static void main(String[] args) { final String text = "abcxaaabbbccyaxbcayaaaxycab"; printMatches("aaa", text); printMatches("abc", text); } private static void printMatches(String word, String text) { System.out.println("matches for "+word +" in "+text+":"); StringBuilder match = new StringBuilder(3); StringBuilder notYetFounds=new StringBuilder(word); for (Character c : text.toCharArray()) { int idx = notYetFounds.indexOf(c.toString()); if (idx!=-1) { notYetFounds.replace(idx,idx+1,""); match.append(c); if (match.length()==word.length()) { System.out.println(match); match = new StringBuilder(3); notYetFounds=new StringBuilder(word); } } else { match = new StringBuilder(3); notYetFounds=new StringBuilder(word); } } System.out.println(); } } 

Это дает мне следующий результат:

 matches for aaa in abcxaaabbbccyaxbcayaaaxycab: aaa aaa matches for abc in abcxaaabbbccyaxbcayaaaxycab: abc bca cab 

Был некоторый бенчмарк, код выше нашел 30815 совпадений «abc» в случайной строке 36M всего за 4,5 секунды. Как сказал Джим, спасибо за эту головоломку …