Какая структура данных и алгоритм подходят для этого?

Question

У меня есть 1000 строк. Учитывая шаблон, который нужно искать во всей строке, и вернуть всю строку, содержащую этот шаблон.

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

int main() { 
    vector <string> v; 
    v.push_back ("maggi"); 
    v.push_back ("Active Baby Pants Large 9-14 Kg "); 
    v.push_back ("Premium Kachi Ghani Pure Mustard Oil "); 
    v.push_back ("maggi soup"); 
    v.push_back ("maggi sauce"); 
    v.push_back ("Superlite Advanced Jar"); 
    v.push_back ("Superlite Advanced"); 
    v.push_back ("Goldlite Advanced"); 
    v.push_back ("Active Losorb Oil Jar"); 

    vector <string> result; 

    string str = "Advanced"; 

    for (unsigned i=0; i<v.size(); ++i) 
    { 
     size_t found = v[i].find(str); 
     if (found!=string::npos) 
      result.push_back(v[i]); 
    } 

    for (unsigned j=0; j<result.size(); ++j) 
    { 
     cout << result[j] << endl; 
    } 
    // your code goes here 
    return 0; 

} 

Есть ли оптимальный способ достижения такого же уровня сложности и меньшей производительности?

Answer 1

Контейнеры, которые я считаю подходящими для вашего приложения.

Однако вместо std::string::find, если вы реализуете свой собственный KMP algorithm, то вы можете гарантировать, что временная сложность будет линейной в терминах длины строки + строки поиска.
http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

Как таковая сложность std::string::find не определена.
http://www.cplusplus.com/reference/string/string/find/

EDIT: Как было отмечено по этой ссылке, если длина ваших строк не велико (более 1000), то, возможно, с помощью std::string::find будет достаточно хорошо, так как здесь табуляция и т.д. не требуется.
C++ string::find complexity

Answer 2

Если результат используется в том же блоке кода, как входной вектор строк (это так в вашем примере), или даже если у вас есть гарантия, что каждый использует результат только тогда, когда вход существует, вы не На самом деле нужно копировать строки. Это может быть дорогостоящая операция, которая значительно замедляет общий алгоритм.

Вместо этого вы могли бы иметь вектор указателей как результат:

vector <string*> result; 

Answer 3

Если список строк «фиксированный» для многих поисков, то вы можете сделать несколько простой предобработку, чтобы ускорить процесс, весьма значительно, используя инвертированный индекс.

Построить карту всех символов, присутствующих в строках, другими словами, для каждого возможного магазина полукокса список всех строк, содержащих этот символ:

std::map< char, std::vector<int> > index; 
std::vector<std::string> strings; 

void add_string(const std::string& s) { 
    int new_pos = strings.size(); 
    strings.push_back(s); 
    for (int i=0,n=s.size(); i<n; i++) { 
     index[s[i]].push_back(new_pos); 
    } 
} 

Затем, когда попросили найти подстроку вы первый чек для всех символов в перевернутом индексировать и перебирать только в списке в индексе с наименьшим количеством записей:

std::vector<std::string *> matching(const std::string& text) { 
    std::vector<int> *best_ix = NULL; 
    for (int i=0,n=text.size(); i<n; i++) { 
     std::vector<int> *ix = &index[text[i]]; 
     if (best_ix == NULL || best_ix->size() > ix->size()) { 
      best_ix = ix; 
     } 
    } 

    std::vector<std::string *> result; 
    if (best_ix) { 
     for (int i=0,n=best_ix->size(); i<n; i++) { 
      std::string& cand = strings[(*best_ix)[i]]; 
      if (cand.find(text) != std::string::npos) { 
       result.push_back(&cand); 
      } 
     } 
    } else { 
     // Empty text as input, just return the whole list 
     for (int i=0,n=strings.size(); i<n; i++) { 
      result.push_back(&strings[i]); 
     } 
    } 
    return result; 
} 

Многие улучшения возможны:

• используйте больший индекс (например, с помощью пары последовательных символов)
• избежать с учетом очень общих символов (остановить списки)
• использование хешей, вычисленных из триплетов или более длинных последовательностей
• поиск перекрестка вместо поиска более короткий список. Учитывая, что элементы добавляются для того, чтобы векторы в любом случае уже отсортированы, а пересечение может быть вычислено эффективно даже с использованием векторов (см. std::set_intersection).

Все они могут иметь смысл или нет в зависимости от параметров проблемы (сколько строк, сколько времени, сколько времени просматривается текст ...).

Answer 4

Если исходный текст является большим и статическим (например, обходные веб-страницы), вы можете сэкономить время поиска, предварительно создавая структуру данных suffix tree или trie. Шаблон поиска может пересекать дерево, чтобы найти совпадения.

Если исходный текст невелик и часто изменяется, тогда ваш оригинальный подход подходит. Функции STL, как правило, очень хорошо оптимизированы и выдержали испытание временем.