C ++: как построить строку пересечения из двух строк, разделенных пробелом? - PullRequest
Новая
       13

C ++: как построить строку пересечения из двух строк, разделенных пробелом?

1 голос
/ 09 августа 2011

У меня есть две строки, разделенные пробелом ... (X не означает один и тот же символ) 

st1 = "abc def kok...."
st2 = "kok bbr def ffe ...."

Я хотел бы построить строку пересечения следующим образом: common = "kok def"

Каков эффективный способ сделать это в C ++?

Спасибо

Ответы [ 3 ]

9 голосов
/ 09 августа 2011

Использование std::set_intersection

Пример программы:

Я предполагаю, что вы уже токенизировали свои строки ( это решение кажется простым в реализации). 

// Data
std::vector<string> a,b;
a.push_back("abc");b.push_back("kok");
a.push_back("def");b.push_back("bbr");
a.push_back("kok");b.push_back("def");
a.push_back("foo");b.push_back("ffe");

// Allocate space for intersection
std::vector<string> v(a.size()+b.size());

// Sort as required by set_intersection
std::sort(a.begin(),a.end());
std::sort(b.begin(),b.end());
// Compute
std::vector<string>::iterator it = std::set_intersection(a.begin(),a.end(),b.begin(),b.end(),v.begin());

// Display
v.erase(it,v.end());
for(std::vector<string>::iterator it = v.begin();it < v.end(); ++it) std::cout<<*it<<std::endl;

Сложность должна составлять O (n log n) в количестве токенов (или подстрок).

2 голосов
/ 09 августа 2011
  1. Разделите st1 на подстроки и поместите их все в std::set
  2. Разделите st2 в подстроки и проверьте для каждой из них, существуют ли они в наборе, созданном на шаге 1.

Это даст O(n log n) время выполнения.Вы должны пройти через обе строки ровно один раз.Вставка и извлечение из набора обычно O(log n) для каждого элемента, что дает O(n log n).

Если вы можете использовать набор на основе хеша (или некоторый другой неупорядоченный набор) с O(1) сложность вставки и извлеченияВы сократите сложность до O(n).

1 голос
/ 09 августа 2011

Чтобы немного расширить ответы, которые вы уже получили, нужно учесть два фактора, которые вы не указали. Во-первых, если на входе есть повторяющиеся элементы, вы хотите, чтобы те рассматривались для вывода. Например, заданный ввод, такой как: 

st1 = "kok abc def kok...."
st2 = "kok bbr kok def ffe ...."

Поскольку «kok» появляется дважды на обоих входах, должен ли «kok» появляться один раз на выходе или дважды?

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

Если вы собираетесь прочитать все входные данные, а затем сгенерировать один выходной сигнал, вы, вероятно, захотите использовать std::vector, за которым следует std::sort. Если вы хотите, чтобы каждый вход появлялся в выходных данных только один раз, независимо от того, как часто он появляется на обоих входах, вы должны следовать за этим std::unique и, наконец, выполнить set_intersection.

Если вы хотите поддерживать итеративные обновления, то вы, вероятно, захотите использовать std::set или std::multiset (std::set для каждого вывода, который будет уникальным, std::multiset, если повторные вводы должны давать повторяющиеся результаты).

Редактировать: из-за отсутствия дублирования во вводе, очень быстрая простая реализация будет выглядеть примерно так: 

#include <string>
#include <set>
#include <algorithm>
#include <iterator>
#include <sstream>
#include <iostream>

int main() {   
    std::string st1("abc def kok");
    std::string st2("kok bbr def ffe");

    std::istringstream s1(st1);
    std::istringstream s2(st2);

    // Initialize stringstreams. Whine about most vexing parse.
    std::set<std::string> words1((std::istream_iterator<std::string>(s1)), 
                                 std::istream_iterator<std::string>());

    std::set<std::string> words2((std::istream_iterator<std::string>(s2)), 
                                 std::istream_iterator<std::string>());

    std::ostringstream common;

    // put the intersection into common:
    std::set_intersection(words1.begin(), words1.end(), 
                          words2.begin(), words2.end(),
                          std::ostream_iterator<std::string>(common, " "));

    std::cout << common.str();  // show the result.
    return 0;
}
...