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

01.01.2020C Программы

Учитывая текст 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 ++ программа для поиска всех анаграмм шаблона в тексте
#include <cstring>
#include <iostream>
#define MAX 256

using namespace std;

// Эта функция возвращает true, если содержимое arr1 [] и arr2 []
// одинаковы, иначе ложно.

bool compare(char arr1[], char arr2[])

{

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

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

return false;

return true;

}

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

void search(char* pat, char* txt)

{

int M = strlen(pat), N = strlen(txt);

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

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

char countP[MAX] = { 0 }, countTW[MAX] = { 0 };

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

(countP[pat[i]])++;

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

}

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

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

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

// количество шаблонов []

if (compare(countP, countTW))

cout << "Found at Index " << (i - M) << endl;

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

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

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

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

}

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

if (compare(countP, countTW))

cout << "Found at Index " << (N - M) << endl;

}

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

int main()

{

char txt[] = "BACDGABCDA";

char pat[] = "ABCD";

search(pat, txt);

return 0;

}

Выход:

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

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

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

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

0.00 (0%) 0 votes