Поиск по шаблону с использованием дерева всех суффиксов

// Простая реализация подстроки в C ++ с использованием трех суффиксов
#include<iostream>
#include<list>
#define MAX_CHAR 256

using namespace std;

  
// Суффикс Trie (Три всех суффиксов) Узел

class SuffixTrieNode

{

private:

    SuffixTrieNode *children[MAX_CHAR];

    list<int> *indexes;

public:

    SuffixTrieNode() // Конструктор

    {

        // Создать пустой связанный список для индексов

        // суффиксы, начинающиеся с этого узла

        indexes = new list<int>;

        // Инициализируем все дочерние указатели как NULL

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

          children[i] = NULL;

    }

    // Рекурсивная функция для вставки суффикса текста

    // в поддереве с этим узлом

    void insertSuffix(string suffix, int index);

    // Функция для поиска шаблона в поддереве с корнем

    // с этим узлом. Функция возвращает указатель на связанный

    // список, содержащий все индексы, в которых присутствует шаблон.

    // Возвращаемые индексы являются индексами последних символов

    // сопоставленного текста.

    list<int>* search(string pat);

};

  
// Три всех суффиксов

class SuffixTrie

{

private:

    SuffixTrieNode root;

public:

    // Конструктор (Создает три суффикса данного текста)

    SuffixTrie(string txt)

    {

        // Рассмотрим все суффиксы заданной строки и вставим

        // их в суффикс Trie с использованием рекурсивной функции

        // insertSuffix () в классе SuffixTrieNode

        for (int i = 0; i < txt.length(); i++)

            root.insertSuffix(txt.substr(i), i);

    }

    // Функция для поиска шаблона в этом суффиксе.

    void search(string pat);

};

  
// Рекурсивная функция для вставки суффикса текста в
// поддерево укоренено в этом узле

void SuffixTrieNode::insertSuffix(string s, int index)

{

    // Сохранить индекс в связанном списке

    indexes->push_back(index);

    // Если в строке больше символов

    if (s.length() > 0)

    {

        // Находим первый символ

        char cIndex = s.at(0);

        // Если для этого символа нет ребра, добавьте новое ребро

        if (children[cIndex] == NULL)

            children[cIndex] = new SuffixTrieNode();

        // Повтор для следующего суффикса

        children[cIndex]->insertSuffix(s.substr(1), index+1);

    }

}

  
// Рекурсивная функция для поиска шаблона в поддереве с корнем
// этот узел

list<int>* SuffixTrieNode::search(string s)

{

    // Если все символы шаблона были обработаны,

    if (s.length() == 0)

        return indexes;

    // если есть ребро от текущего узла суффикса trie,

    // следуем за краем.

    if (children[s.at(0)] != NULL)

        return (children[s.at(0)])->search(s.substr(1));

    // Если края нет, шаблон не существует в тексте

    else return NULL;

}

  
/ * Печатает все вхождения pat в суффиксе Trie S (построено для текста) * /

void SuffixTrie::search(string pat)

{

    // Давайте назовем рекурсивную функцию поиска для корня Trie.

    // Мы получаем список всех индексов (где pat присутствует в тексте) в

    // переменная 'result'

    list<int> *result = root.search(pat);

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

    if (result == NULL)

        cout << "Pattern not found" << endl;

    else

    {

       list<int>::iterator i;

       int patLen = pat.length();

       for (i = result->begin(); i != result->end(); ++i)

         cout << "Pattern found at position " << *i - patLen<< endl;

    }

}

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

int main()

{

    // Давайте создадим три-суффикс для текста "geeksforgeeks.org"

    string txt = "geeksforgeeks.org";

    SuffixTrie S(txt);

    cout << "Search for 'ee'" << endl;

    S.search("ee");

    cout << "\nSearch for 'geek'" << endl;

    S.search("geek");

    cout << "\nSearch for 'quiz'" << endl;

    S.search("quiz");

    cout << "\nSearch for 'forgeeks'" << endl;

    S.search("forgeeks");

    return 0;

}

import java.util.LinkedList;

import java.util.List;

class SuffixTrieNode {

    final static int MAX_CHAR = 256;

    SuffixTrieNode[] children = new SuffixTrieNode[MAX_CHAR];

    List<Integer> indexes;

    SuffixTrieNode() // Конструктор

    {

        // Создать пустой связанный список для индексов

        // суффиксы, начинающиеся с этого узла

        indexes = new LinkedList<Integer>();

        // Инициализируем все дочерние указатели как NULL

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

            children[i] = null;

    }

    // Рекурсивная функция для вставки суффикса

    // текст в поддереве с корнем из этого узла

    void insertSuffix(String s, int index) {

        // Сохранить индекс в связанном списке

        indexes.add(index);

        // Если в строке больше символов

        if (s.length() > 0) {

            // Находим первый символ

            char cIndex = s.charAt(0);

            // Если для этого символа нет ребра,

            // добавить новое ребро

            if (children[cIndex] == null)

                children[cIndex] = new SuffixTrieNode();

            // Повтор для следующего суффикса

            children[cIndex].insertSuffix(s.substring(1),

                                              index + 1);

        }

    }

    // Функция для поиска шаблона в поддереве с корнем

    // с этим узлом. Функция возвращает указатель на

    // связанный список, содержащий все индексы, где шаблон

    // настоящее. Возвращенные индексы являются индексами

    // последние символы сопоставленного текста.

    List<Integer> search(String s) {

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

        // обработанный,

        if (s.length() == 0)

            return indexes;

        // если есть ребро от текущего узла

        // дерево суффиксов, следуем за краем.

        if (children[s.charAt(0)] != null)

            return (children[s.charAt(0)]).search(s.substring(1));

        // Если ребра нет, шаблон не существует в

        // текст

        else

            return null;

    }

}

  
// Три всех суффиксов

class Suffix_tree{

    SuffixTrieNode root = new SuffixTrieNode();

    // Конструктор (Строит три суффикса из

    // заданный текст)

    Suffix_tree(String txt) {

        // Рассмотрим все суффиксы данной строки и

        // вставляем их в суффикс Trie, используя

        // рекурсивная функция insertSuffix () в

        // SuffixTrieNode class

        for (int i = 0; i < txt.length(); i++)

            root.insertSuffix(txt.substring(i), i);

    }

    / * Печатает все вхождения pat в Suffix Trie S

    (построено для текста) * /

    void search_tree(String pat) {

        // Давайте вызовем рекурсивную функцию поиска для

        // корень три.

        // Получаем список всех индексов (где pat

        // присутствует в тексте) в переменной 'result'

        List<Integer> result = root.search(pat);

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

        if (result == null)

            System.out.println("Pattern not found");

        else {

            int patLen = pat.length();

            for (Integer i : result)

                System.out.println("Pattern found at position " +

                                                (i - patLen));

        }

    }

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

    public static void main(String args[]) {

        // Давайте построим суффикс три для текста

        // "geeksforgeeks.org"

        String txt = "geeksforgeeks.org";

        Suffix_tree S = new Suffix_tree(txt);

        System.out.println("Search for 'ee'");

        S.search_tree("ee");

        System.out.println("\nSearch for 'geek'");

        S.search_tree("geek");

        System.out.println("\nSearch for 'quiz'");

        S.search_tree("quiz");

        System.out.println("\nSearch for 'forgeeks'");

        S.search_tree("forgeeks");

    }

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

// C # реализация подхода

using System;

using System.Collections.Generic;

class SuffixTrieNode

{

    static int MAX_CHAR = 256;

    public SuffixTrieNode[] children = new SuffixTrieNode[MAX_CHAR];

    public List<int> indexes;

    public SuffixTrieNode() // Конструктор

    {

        // Создать пустой связанный список для индексов

        // суффиксы, начинающиеся с этого узла

        indexes = new List<int>();

        // Инициализируем все дочерние указатели как NULL

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

            children[i] = null;

    }

    // Рекурсивная функция для вставки суффикса

    // текст в поддереве с корнем из этого узла

    public void insertSuffix(String s, int index) 

    {

        // Сохранить индекс в связанном списке

        indexes.Add(index);

        // Если в строке больше символов

        if (s.Length > 0)

        {

            // Находим первый символ

            char cIndex = s[0];

            // Если для этого символа нет ребра,

            // добавить новое ребро

            if (children[cIndex] == null)

                children[cIndex] = new SuffixTrieNode();

            // Повтор для следующего суффикса

            children[cIndex].insertSuffix(s.Substring(1),

                                              index + 1);

        }

    }

    // Функция для поиска шаблона в поддереве с корнем

    // с этим узлом. Функция возвращает указатель на

    // связанный список, содержащий все индексы, где шаблон

    // настоящее. Возвращенные индексы являются индексами

    // последние символы сопоставленного текста.

    public List<int> search(String s) 

    {

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

        // обработанный,

        if (s.Length == 0)

            return indexes;

        // если есть ребро от текущего узла

        // дерево суффиксов, следуем за краем.

        if (children[s[0]] != null)

            return (children[s[0]]).search(s.Substring(1));

        // Если ребра нет, шаблон не существует в

        // текст

        else

            return null;

    }

}

  
// Три всех суффиксов

public class Suffix_tree

{

    SuffixTrieNode root = new SuffixTrieNode();

    // Конструктор (Строит три суффикса из

    // заданный текст)

    Suffix_tree(String txt) 

    {

        // Рассмотрим все суффиксы данной строки и

        // вставляем их в суффикс Trie, используя

        // рекурсивная функция insertSuffix () в

        // SuffixTrieNode class

        for (int i = 0; i < txt.Length; i++)

            root.insertSuffix(txt.Substring(i), i);

    }

    / * Печатает все вхождения pat в

    Суффикс Trie S (построен для текста) * /

    void search_tree(String pat) 

    {

        // Давайте вызовем рекурсивную функцию поиска

        // для корня Trie.

        // Получаем список всех индексов (где pat

        // присутствует в тексте) в переменной 'result'

        List<int> result = root.search(pat);

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

        if (result == null)

            Console.WriteLine("Pattern not found");

        else 

        {

            int patLen = pat.Length;

            foreach (int i in result)

                Console.WriteLine("Pattern found at position " +

                                                  (i - patLen));

        }

    }

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

    public static void Main(String []args) 

    {

        // Давайте построим суффикс три для текста

        // "geeksforgeeks.org"

        String txt = "geeksforgeeks.org";

        Suffix_tree S = new Suffix_tree(txt);

        Console.WriteLine("Search for 'ee'");

        S.search_tree("ee");

        Console.WriteLine("\nSearch for 'geek'");

        S.search_tree("geek");

        Console.WriteLine("\nSearch for 'quiz'");

        S.search_tree("quiz");

        Console.WriteLine("\nSearch for 'forgeeks'");

        S.search_tree("forgeeks");

    }

}

  
// Этот код предоставлен 29AjayKumar