Рубрики

Поиск подстроки 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

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

Эта проблема немного отличается от стандартной задачи поиска по шаблону, здесь мы также должны искать анаграммы. Поэтому мы не можем напрямую применять стандартные алгоритмы поиска шаблонов, такие как KMP , Рабин Карп , Бойер Мур и т. Д.

Простая идея — модифицировать алгоритм Рабина Карпа . Например, мы можем сохранить значение хеш-функции как сумму значений 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<iostream>
#include<cstring>
#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;

}

Джава

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

python3

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

  

MAX=256 

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

def compare(arr1, arr2):

    for i in range(MAX):

        if arr1[i] != arr2[i]:

            return False

    return True

      
# Эта функция поиска для всех
# перестановки pat [] в txt []

def search(pat, txt):

  

    M = len(pat)

    N = len(txt)

  

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

    # все символы шаблона

    # countTW []: Сохранить количество

    # текущее окно текста

    countP = [0]*MAX

  

    countTW = [0]*MAX

  

    for i in range(M):

        (countP[ord(pat[i]) ]) += 1

        (countTW[ord(txt[i]) ]) += 1

  

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

    # символов шаблона

    for i in range(M,N):

  

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

        # окно текста с

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

        if compare(countP, countTW):

            print("Found at Index", (i-M))

  

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

        (countTW[ ord(txt[i]) ]) += 1

  

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

        (countTW[ ord(txt[i-M]) ]) -= 1

      

    # Проверьте последнее окно в тексте

    if compare(countP, countTW):

        print("Found at Index", N-M)

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

txt = "BACDGABCDA"

pat = "ABCD"       
search(pat, txt)   

  
# Этот код добавлен
# Упендра Сингх Бартвал

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 (или поиск всех перестановок)

0.00 (0%) 0 votes