Поиск шаблона в заданной строке

Опубликовано: 19 Сентября, 2022

Даны две строки, текст и шаблон размером N и M (N > M) соответственно, задача состоит в том, чтобы напечатать все вхождения шаблона в тексте .

Примеры:

Input: text = “This is a dummy text”,  pattern = “This”
Output: Pattern found at indices: 0
Explanation: The pattern “This” starts from index 0 in the given text.

Input: text = “Welcome to Geeks for Geeks”,  pattern = “Geeks”
Output: Pattern found at indices: 21 11
Explanation: The pattern “Geeks” starts from the 11th and 21st index (considering the white spaces).

Подход: Подход к этой проблеме основан на следующей идее:

Find the possible starting indices of all the starting points in the text. Then for all those indices check if their adjacents match with the next elements of the pattern.

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

  • Прежде всего, используйте массив unordered_set размером 256. Пройдитесь по тексту и вставьте каждый индекс в набор соответствующего символа.

C++




for (int i = 0; i < st.length(); i++)
    // Insert every index to the hash set using character
    // ASCII.
    structured_text[st[i]].insert(i);

  • Найдите первый символ шаблона в массиве и поместите каждый индекс, содержащийся в хэш-наборе, в очередь.
C++



for (int ind : structured_text[pattern[0]])
    q_indices.push(ind);
  • Затем перейдите по шаблону от i = 1 до M-1 :
    •  Если индекс вstructured_text[pattern[i]] находится рядом с любым из символов, присутствующих в pat[i-1] , поместите его в очередь для следующей итерации.
    •  В противном случае продолжайте проверку других позиций.
C++



for (int i = 1; i < pattern.length(); i++) {
    char ch = pattern[i];
    int q_size = q_indices.size();
    /*  the queue contains the number of occurrences of the
    previous character. traverse the queue for q_size times
    Check the next character of the pattern found or not. */
    while (q_size--) {
        int ind = q_indices.front();
        q_indices.pop();
        if (structured_text[ch].find(ind + 1)
            != structured_text[ch].end())
            q_indices.push(ind + 1);
    }
}
  • Если весь шаблон найден, верните эти индексы.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N * logK), где K — максимальное появление любого символа.
 Вспомогательное пространство: O (d), d представляет собой массив unordered_set размером 256

            

                            

                    
                                    

                        

                
РЕКОМЕНДУЕМЫЕ СТАТЬИ