Суффикс Диапазон с ++ - PullRequest
Новая
       26

Суффикс Диапазон с ++

4 голосов
/ 23 августа 2011

Я пытаюсь построить диапазон суффиксов, равный

если у меня есть строки "каталог" "катализатор" "бан" "бань"

тогда дерево суффиксов будет похоже на 

                            .
                           / \
                          c   b
                         /     \
                        a       a
                       /         \
                      t           n
                     / \         / \        
                    a   a       $   y 
                   /     \         / \
                  l       l       $    $
                 /         \
                o           y         
               /             \
              g               s
             / \               \
            $   $               t
                                /\
                               $   $

Теперь я хочу найти диапазон суффиксов каждой строки ... что если я возьму строку "Cat", то она должна дать мне диапазон, включающий все его суффиксы, к которым префикс "cat". Мне нужно использовать часовые для разделения каждой строки .. может быть "$"

Может ли кто-нибудь предложить мне лучший способ выяснить это с помощью c ++. Любые ссылки будут полезны. спасибо

Ответы [ 4 ]

2 голосов
/ 23 августа 2011

Гораздо проще ответ, чем мой первый.У вас есть std :: set of strings: 

typedef std::set<std::string>::iterator iter_type;
std::set<std::string> data;

и функция с именем find (), которая возвращает пару итераторов.Первый итератор указывает на начало строк, которые соответствуют префиксу, а последний итератор - один после последней строки, которая соответствует префиксу.Если у вас есть 10000 строк, нужно проверить только около 26 из них. 

std::pair<iter_type, iter_type> find(std::string substr) {
   std::pair<iter_type, iter_type> r;
   r.first = data.lower_bound(substr);
   substr[substr.size()-1]++; //I'm assuming substr is at least one character
   r.second = data.upper_bound(substr);
   return r;
}

Затем, после загрузки данных, вы просто вызываете функцию find (...), и она возвращаетпара итераторов, указывающая на нужные вам строки.Вы можете использовать их в качестве входных данных для любого стандартного алгоритма или делать что угодно. 

int main() {
    data.insert("catalog");
    data.insert("catalyst");
    data.insert("ban");
    data.insert("bany");
    //find the region of strings beginning with "cat"
    std::pair<iter_type, iter_type> range = find("cat");
    //display them all
    for(iter_type i=range.first; i!=range.second; ++i)
        std::cout << *i << '\n';
}
1 голос
/ 23 августа 2011

Решение 1. Эффективное использование пространства. Использование структуры данных Trie (один символ - один узел, один узел может указывать на 26 разных узлов). Найти последний узел для данного префикса.Напечатайте префикс + 'путь ко всем терминальным узлам'

Решение 2. Экономия времени, если вы заинтересованы только в первых трех префиксных символах.Создайте 3d массив 

 vector<string> arr[27][27][27]

Вставка.если вы хотите вставить
слово: ABCD arr [A] [B] [C] .push_back ("D") слово: BBBX arr [B] [B] [B] .push_back ("X")

Печать: vector & a = arr [char1] [char2] [char3] для (строка s в a) char1-char2-char3 + s

0 голосов
/ 24 августа 2011

Вот, я думаю, самый краткий ответ.:) 

set<string> s;
string word = "ABC"
//Inserts.
// e.g. s.insert("ABCD");

for(set<string>::iterator it=s.begin();it!=s.end();++it)
    if(!(*it).compare(0,word.size(),word))
        cout<<*it<<endl;

Протестированный код!: P

0 голосов
/ 23 августа 2011

Я разместил алгоритм для решения удивительно похожей проблемы на Есть ли подходящая структура данных для решения этого вопроса? .Сначала мы создаем дерево суффиксов узлов, подобное 

class node { //create a prefix node type
    node & operator=(const node & b); //UNDEFINED, NO COPY
    node & operator=(const node && b); //UNDEFINED, NO COPY
    node * next[27];  // pointers to nodes of the next letter (27th letter is $)
public:
    node(); 
    ~node();
    void add(char* mystring);
    void find(char* mystring, 
        std::vector<std::pair<int, std::string>>& out, 
        std::string sofar="");
}root;

, и заполняем его.Затем, чтобы найти все подстроки «cata», мы перебираем дерево по буквам в «cata» (root [3] -> [0] -> ['t' - 'a'?] -> [0]) и следите за строкой sofar.Когда мы достигаем конца mystring, мы рекурсивно пытаемся идти вниз по каждому дочернему элементу, а не только по тем, которые соответствуют подстроке, и везде, где мы находим «конец» (буква 27), мы нажимаем sofar на out.Затем мы просто возвращаем, и out содержит все полные строки, начинающиеся с "cata".

...