Рубрики

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

C# Программы

Учитывая текст 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) Последнее окно не проверяется вышеуказанным циклом, поэтому проверьте его явно.

C #

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

using System;

  

class GFG {

    public const int MAX = 256;

  

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

    // содержимое arr1 [] и arr2 []

    // одинаковы, иначе ложно.

    public static bool compare(char[] arr1,

                               char[] arr2)

    {

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

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

                return false;

            }

        }

        return true;

    }

  

    // Эта функция поиска для всех

    // перестановки pat [] в txt []

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

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

        }

  

        // Пройти через оставшиеся

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

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

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

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

            if (compare(countP, countTW)) {

                Console.WriteLine("Found at Index " + (i - M));

            }

  

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

            // текущее окно

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

  

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

            // предыдущее окно

            countTW[txt[i - M]]--;

        }

  

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

        if (compare(countP, countTW)) {

            Console.WriteLine("Found at Index " + (N - M));

        }

    }

  

    // Код драйвера

    public static void Main(string[] args)

    {

        string txt = "BACDGABCDA";

        string pat = "ABCD";

        search(pat, txt);

    }

}

  
// Этот код добавлен
// от Shrikant1

Выход:

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

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

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

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

0.00 (0%) 0 votes