C++:如何构建两个空格分隔的字符串的交集字符串？

Question

我有两个空格分隔的字符串...(X不代表相同的符号)

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

我想构建一个交集字符串,如下所示: common = "kok def"

在c ++中这样做的有效方法是什么？

谢谢

Answer 1

使用 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).