Оптимальный алгоритм поиска анаграмм строки в другой строке

Question

Я наткнулся на эту топи c в книге «Взлом кодирования». Задача состоит в том, чтобы найти перестановки данной меньшей строки s в большей строке b. Я мог бы придумать приведенный ниже алгоритм, временная сложность которого O (B x S), где S и B - длины заданных строк меньшего и большего размера соответственно:

import java.util.HashMap;
public class AnagramAlgorithm {
public static void main(String[] args) {
    String s = "cbabadcbbabbcbabaabccbabc";
    String b = "abbc";

    printAnagramsOfB(s, b);
}

public static void printAnagramsOfB(String text, String pattern) {
    if(isEmpty(text) || isEmpty(pattern)) {
        System.out.println("Invalid Strings");
        return;
    }
    int patternLength = pattern.length();
    for (int i = 0; i < text.length() - patternLength + 1; i++) {
        String substring = text.substring(i, i + patternLength);
        if (isAnagram(pattern, substring)) {
            System.out.println("Anagram Found : " + substring);
        }
    }
}

public static boolean isEmpty(CharSequence str) {
    return str == null || str.length() == 0;
}

public static boolean isAnagram(String pattern, String substring) {
    if (pattern.length() != substring.length()) {
        System.out.println("SubString length doesn't match the length of Given String");
        return false;
    }
    char[] subStringArr = substring.toCharArray();
    char[] patternArr = pattern.toCharArray();
    HashMap<Character, Integer> mapPattern = new HashMap<>();
    HashMap<Character, Integer> mapSubstring = new HashMap<>();
    for (int i = 0; i < subStringArr.length; i++) {
        if (mapSubstring.containsKey(subStringArr[i])) {
            int count = mapSubstring.get(subStringArr[i]);
            mapSubstring.put(subStringArr[i], count + 1);
        } else {
            mapSubstring.put(subStringArr[i], 1);
        }
        if (mapPattern.containsKey(patternArr[i])) {
            int count = mapPattern.get(patternArr[i]);
            mapPattern.put(patternArr[i], count + 1);
        } else {
            mapPattern.put(patternArr[i], 1);
        }
    }
    return mapPattern.equals(mapSubstring);
}
}

В книге упоминается, что наиболее оптимальным Алгоритм имеет O (B). Я не мог придумать такой алгоритм. Согласно моим мыслям, для общей сложности, чтобы быть O (B), алгоритм, чтобы найти, является ли подстрока анаграммой, должен быть O (1), т.е. без каких-либо циклов. Это вообще возможно? Или есть другой способ реализовать наиболее оптимальный алгоритм?

Answer 1

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

public class Solver {

    List<Integer> solve(String t, String s) {

        HashMap<Character, Integer> charCountInT = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            Character c = t.charAt(i);
            if (charCountInT.containsKey(c)) {
                charCountInT.put(c, charCountInT.get(c) + 1);
            }
            else {
                charCountInT.put(c, 1);
            }
        }

        HashMap<Character, Integer> extraCharacters = new HashMap<>();
        for (Character c : charCountInT.keySet()) {
            extraCharacters.put(c, -charCountInT.get(c));
        }
        for (int i = 0; i < t.length(); i++) {
            Character c = s.charAt(i);
            if (extraCharacters.containsKey(c)) {
                extraCharacters.put(c, extraCharacters.get(c) + 1);
            }
        }

        int expectedZeroesInExtraCharacters = charCountInT.size();
        int zeroesInExtraCharacters = 0;
        for (Integer count : extraCharacters.values()) {
            if (count == 0) ++zeroesInExtraCharacters;
        }

        List<Integer> answer = new ArrayList<>();
        if (zeroesInExtraCharacters == expectedZeroesInExtraCharacters) answer.add(0);

        for (int i = 1; i < s.length() - t.length(); i++) {

            Character nextChar = s.charAt(t.length() + i - 1);
            if (charCountInT.containsKey(nextChar)) {
                extraCharacters.put(nextChar, extraCharacters.get(nextChar) + 1);
                if (extraCharacters.get(nextChar) == 0) ++zeroesInExtraCharacters;
                if (extraCharacters.get(nextChar) == 1) --zeroesInExtraCharacters;
            }

            Character removedChar = s.charAt(i - 1);
            if (charCountInT.containsKey(removedChar)) {
                extraCharacters.put(removedChar, extraCharacters.get(removedChar) - 1);
                if (extraCharacters.get(removedChar) == 0) ++zeroesInExtraCharacters;
                if (extraCharacters.get(removedChar) == -1) --zeroesInExtraCharacters;
            }

            if (zeroesInExtraCharacters == expectedZeroesInExtraCharacters) answer.add(i);
        }

        return answer;

    }

    public static void main(String[] args) {
        String t = "abbc";
        String s = "cbabadcbbabbcbabaabccbabc";
        List<Integer> startIndices = new Solver().solve(t, s);
        System.out.println(startIndices);
        for (int startIndex : startIndices) {
            System.out.println(s.substring(startIndex, startIndex + t.length()));
        }
    }

}

Answer 2

Стандартный метод поиска анаграммы использует отсортированную версию для сравнения. Вы не ищите «TARGET», вы сначала помещаете его в алфавитном порядке: «AEGRTT» и ищете его.

Возьмите соответствующее число символов, шесть для «AEGRTT», с начала большего строка. Сортировка и сравнение, чтобы увидеть, если у вас есть совпадение. Затем опустите первую букву и добавьте следующую букву из длинного списка в соответствующую позицию - список уже отсортирован, что поможет. Сравните еще раз и повторите.