我试图找到一个最佳的方式来找到一个字符串的模式和比较。例如,我有s1 = "红蓝蓝红红黄", s2 = "abbaac"。这是匹配的,因为它们有相同的图案。
我的想法是遍历s1和s2,使用vector容器记录相应位置的计数(对于s1将是对应的单词计数,对于s2将是对应的字母计数),然后比较。
这是非常低效的,因为我遍历了整个s1和s2。如果s1 = "红蓝红红红黄", s2 = "abbaac"。在第三个红色之后,基本上没有必要继续迭代它。
那么,关于如何做到这一点,有更好的主意吗?
代码:#include "stdafx.h"
#include <iostream>
#include <string>
#include <array>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> findPattern(string pattern){
vector<int> counts;
for (int i = 0; i < pattern.size(); ++i){
counts.push_back(0);
int counter = 0;
for (int j = i + 1; j < pattern.size(); ++j){
if (pattern[i] == pattern[j]){
++counter;
}
counts[i] = counter;
}
}
return counts;
}
vector<int> findPatternLong(string pattern){
istringstream iss (pattern);
string word;
vector<string> v;
while (iss >> word){
v.push_back(word);
}
vector<int> counts2;
for (int i = 0; i < v.size(); ++i){
counts2.push_back(0);
int counter = 0;
for (int j = i + 1; j < v.size(); ++j){
if (v[i] == v[j]){
++counter;
}
counts2[i] = counter;
}
}
return counts2;
}
int main(int argc, char * argv[]){
vector<int> v1 = findPattern("abbaac");
vector<int> v2 = findPatternLong("red blue blue red red yellow");
if (v1.size() == v2.size()){
for (int i = 0; i < v1.size(); ++i){
if (v1[i] != v2[i]){
cout << "Unmatch" << endl;
return false;
}
}
cout << "match" << endl;
return true;
} else
cout << "Unmatch" << endl;
return 0;
}
@Tony用同样的想法打败了我,但是因为我已经输入了这个,这里是:-)
首先,不要太担心效率,而要关注正确性:的确,过早的优化是万恶之源。编写测试用例,并确保您的代码通过每个测试用例。
第二,我想我会从map/dictionary D开始,并有一个循环,我将解析每个字符串的一个元素(s1中的一个单词,我们称之为"w",s2中的一个字符,假设为"c"),选择一个元素作为键(假设为"c"字符),并检查"c"是否已经在字典中有一个条目:
- 如果同时没有元素,字符串匹配
- 如果我们用完了一边的元素,我们知道没有匹配
- 如果"c"在D中没有条目,则存储当前值:D[c] = w;
- else如果"c"已经有一个条目,检查该条目是否与字符串上找到的值匹配:是D[c] == w?如果没有,我们就知道没有匹配
如果该代码有效,则可以开始优化。在您的示例中,也许我们可以使用一个简单的数组而不是字典,因为ASCII字符是一个小的有限集合。
这不是最有效的代码,但接近最简单的:
std::map<char, std::string> letter_to_word;
std::set<std::string> words_seen;
std::istringstream iss(s1);
std::string word;
for (std::string::size_t i = 0; i < s2.size(); ++i)
{
if (!(iss >> word))
return false; // more letters than words
std::string& expected_word = letter_to_word[s2[i]];
if (expected_word == "")
{
// if different letters require different words...
if (words_seen.find(word) != words_seen.end())
return false; // multiple letters for same word
words_seen.insert(word);
expected_word = word; // first time we've seen letter, remember associated word
}
else if (expected_word != word)
return false; // different word for same letter
}
return !(iss >> word); // check no surplus words
你不需要两个向量
处理第二个字符串时,将第一个模式的计数与第一个条目进行比较。如果匹配,继续,否则停止。重复第二串中其余的模式。
不需要存储第二个字符串的模式计数。
编辑
我刚刚读到这个问题有一个字符串中的模式,这个答案与比较不同类型的集合有关。我想答案仍然保持一个小水,如果两个输入字符串首先转换:)
我不会说这是最有效的解决方案,但我喜欢它的可扩展性。
首先是PatternResult
类。它存储模式的结果:
class PatternResult {
private:
std::vector<int> result_;
public:
PatternResult(const std::vector<int>& result) : result_(result) {
};
bool operator == (const PatternResult& rhs) const {
if(result_.size() != rhs.result_.size())
return false;
else {
for(std::vector<int>::size_type r(0);
r < result_.size();
++r) {
if(result_[r] != rhs.result_[r])
return false;
};
return true;
};
};
}; // eo class PatternResult
接受一个整型向量,其值表示它的值。我们重载==
来比较两个模式结果,这意味着它们具有相同的序列,而不管源数据的。
template<class T>
class PatternCounter {
private:
typedef std::vector<T> vec_type;
typedef std::map<T, int> map_type;
map_type found_;
int counter_;
public:
PatternCounter() : counter_(1) {
};
PatternResult count(const vec_type& input ){
std::vector<int> ret;
for(vec_type::const_iterator cit(input.begin());
cit != input.end();
++cit) {
if(found_.find(*cit) != found_.end()) {
ret.push_back(found_[*cit]);
} else {
found_[*cit] = counter_;
ret.push_back(counter_);
++counter_;
};
};
return PatternResult(ret);
};
};
我们做完了。测试代码:
std::vector<std::string> inp1;
inp1.push_back("red");
inp1.push_back("blue");
inp1.push_back("blue");
inp1.push_back("red");
inp1.push_back("yellow");
std::vector<char> inp2;
inp2.push_back('a');
inp2.push_back('b');
inp2.push_back('b');
inp2.push_back('a');
inp2.push_back('c');
PatternCounter<std::string> counter1;
PatternCounter<char> counter2;
PatternResult res1(counter1.count(inp1));
PatternResult res2(counter2.count(inp2));
if(res1 == res2) {
// pattern sequences are equal
};
注意,这是快速和肮脏的,我相信它可以做得更有效率。
基本上,您希望检查序列是否遵循相同的顺序。你不用担心顺序到底是什么:第一,第二,第一,第三,已经足够好了。现在,你可以用一个容器来做这件事,它以某种方式将字符串映射到整型。然而,您将存储每个字符串的副本,并且忽略了您并不真正关心字符串值的事实。对于微小的测试用例,这无关紧要,但是对于大量的长单词序列,您会在不需要的时候迅速消耗内存。
那么让我们利用我们不关心字符串值或存储它们的事实。如果是这种情况,我们可以使用哈希函数将字符串转换为简单的size_t值,并强有力地保证它们是唯一的。然而,哈希值不是连续的,我们需要根据哈希值检索序列。记录它们序列的最简单方法是将它们映射到地图的大小,以便于查找。最后一个难题是检查哈希值是否在相同的序列中。
我还假设你不只是想比较一个句子和一个单词,而是两个单词或两个句子。下面是一个快速的c++ 11示例,它基本上完成了上述操作,并且除非需要,否则不会在内存中保存任何内容。
当然,这仍然可以进一步优化——例如,并行执行。#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <sstream>
/*
s1 = "red blue blue red red yellow"
s2 = "abbaac"
This would match because they have the same pattern.
*/
typedef std::map<size_t,size_t> hash_map;
typedef std::vector<std::string> wordlist;
size_t ordered_symbol( hash_map &h, std::string const& word )
{
std::hash<std::string> hash_fn;
size_t hash = hash_fn(word);
if(h.find(hash)==h.end())
{
size_t const sequence = h.size();
h[hash] = sequence;
return sequence;
}
return h[hash];
}
wordlist create_wordlist( std::string const& str )
{
if(str.find_first_of(' ') != std::string::npos)
{
wordlist w1;
std::stringstream sstr(str);
std::string s;
while(sstr>>s)
w1.push_back(s);
return w1;
}
wordlist w2;
for(auto i : str)
{
std::string s;
s.append(1,i);
w2.push_back(s);
}
return w2;
}
bool pattern_matches( std::string const& s1, std::string const& s2 )
{
wordlist const w1 = create_wordlist(s1);
wordlist const w2 = create_wordlist(s2);
if(w1.size()!=w2.size())
return false;
hash_map h1,h2;
for( size_t i = 0; i!=w1.size(); ++i)
if(ordered_symbol(h1,w1[i])!=ordered_symbol(h2,w2[i]))
return false;
return true;
}
void test( std::string const& s1, std::string const& s2 )
{
std::cout<<"["<<s1<<"] "
<<(pattern_matches(s1,s2)? "<==>" : "<=!=>")
<<"["<<s2<<"]n";
}
int main()
{
test("red blue blue red red yellow","abbaac");
test("red blue blue red red yellow","first second second first first third");
test("abbaac","12211g");
test("abbaac","red blue blue red red yellow");
test("abbgac","red blue blue red red yellow");
return 0;
}
//Output:
//[red blue blue red red yellow] <==>[abbaac]
//[red blue blue red red yellow] <==>[first second second first first third]
//[abbaac] <==>[12211g]
//[abbaac] <==>[red blue blue red red yellow]
//[abbgac] <=!=>[red blue blue red red yellow]
编辑:这是一个非c++ 11版本,应该在VS2010上工作。然而,由于c++ 03在标准库中不包括字符串哈希函数,因此本例使用了一个来自堆栈溢出的哈希函数。如果您可以访问boost库,那么使用这个哈希函数会更好。