Рубрики

Java-программа для поиска подстрок Anagram (или поиск всех перестановок)

Учитывая текст txt [0..n-1] и шаблон pat [0..m-1], напишите функцию поиска (char pat [], char txt []), которая печатает все вхождения pat [] и его перестановки (или анаграммы) в txt []. Вы можете предположить, что n> m.
Ожидаемая сложность времени O (n)

Примеры:

1) Input:  txt[] = "BACDGABCDA"  pat[] = "ABCD"
   Output:   Found at Index 0
             Found at Index 5
             Found at Index 6
2) Input: txt[] =  "AAABABAA" pat[] = "AABA"
   Output:   Found at Index 0
             Found at Index 1
             Found at Index 4

Мы настоятельно рекомендуем вам нажать здесь и попрактиковаться, прежде чем переходить к решению.

Простая идея — модифицировать алгоритм Рабина Карпа . Например, мы можем сохранить значение хеш-функции как сумму значений ASCII всех символов по модулю большого простого числа. Для каждого символа текста мы можем добавить текущий символ к значению хеша и вычесть первый символ предыдущего окна. Это решение выглядит хорошо, но, как и в случае со стандартным Рабином Карпом, временная сложность этого решения в наихудшем случае — O (mn). Наихудший случай возникает, когда все значения хеш-функции совпадают, и мы одно за другим сопоставляем все символы.
Мы можем достичь O (n) временной сложности, предполагая, что размер алфавита фиксирован, что, как правило, верно, поскольку у нас есть максимально 256 возможных символов в ASCII. Идея состоит в том, чтобы использовать два массива счета:

1) Первый массив подсчета хранит частоты символов в шаблоне.
2) Второй массив подсчета хранит частоты символов в текущем окне текста.

Важно отметить, что временная сложность сравнения двух массивов счетчиков равна O (1), поскольку количество элементов в них фиксировано (независимо от размера рисунка и текста). Ниже приведены шаги этого алгоритма.
1) Сохранение подсчетов частот паттерна в первом массиве countP [] . Также храните подсчеты частот символов в первом окне текста в массиве countTW [] .

2) Теперь запустите цикл от i = M до N-1. Делайте следующее в цикле.
… ..A) Если два массива подсчета идентичны, мы нашли случай.
… ..B) Увеличение счетчика текущего символа текста в countTW []
… ..C) Уменьшить счетчик первого символа в предыдущем окне в countWT []

3) Последнее окно не проверяется вышеуказанным циклом, поэтому проверьте его явно.

Джава

// Java программа для поиска всех анаграмм
// шаблона в тексте

public class GFG {

    static final int MAX = 256;

  

    // Эта функция возвращает true, если содержимое

    // из arr1 [] и arr2 [] совпадают, иначе

    // ложный.

    static boolean compare(char arr1[], char arr2[])

    {

        for (int i = 0; i < MAX; i++)

            if (arr1[i] != arr2[i])

                return false;

        return true;

    }

  

    // Эта функция ищет все перестановки

    // из pat [] в txt []

    static void search(String pat, String txt)

    {

        int M = pat.length();

        int N = txt.length();

  

        // countP []: сохранить количество всех

        // символы шаблона

        // countTW []: Сохранить счетчик текущего

        // окно текста

        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)])++;

        }

  

        // Обход оставшихся символов

        // шаблона

        for (int i = M; i < N; i++) {

            // Сравнить счетчики текущего окна

            // текста с количеством паттернов []

            if (compare(countP, countTW))

                System.out.println("Found at Index " + (i - M));

  

            // Добавить текущий символ к текущему

            // окно

            (countTW[txt.charAt(i)])++;

  

            // Удалить первый символ предыдущего

            // окно

            countTW[txt.charAt(i - M)]--;

        }

  

        // Проверяем последнее окно в тексте

        if (compare(countP, countTW))

            System.out.println("Found at Index " + (N - M));

    }

  

    / * Программа драйвера для проверки вышеуказанной функции * /

    public static void main(String args[])

    {

        String txt = "BACDGABCDA";

        String pat = "ABCD";

        search(pat, txt);

    }

}
// Этот код предоставлен Sumit Ghosh

Выход:

Found at Index 0
Found at Index 5
Found at Index 6

Пожалуйста, обратитесь к полной статье о поиске подстроки Anagram (или Поиск всех перестановок) для более подробной информации!

Рекомендуемые посты:

Java-программа для поиска подстрок Anagram (или поиск всех перестановок)

0.00 (0%) 0 votes