0

我正在尝试找到一种最佳方法来查找字符串模式并进行比较。例如，我有 s1 =“红蓝蓝红红黄”和 s2 =“ abbaac ”。这将匹配，因为它们具有相同的模式。

我这样做的想法是遍历 s1 和 s2，使用向量容器记录相应位置的计数（对于 s1 将是相应的单词数，对于 s2 将是相应的字母数），然后进行比较。

这确实效率低下，因为我遍历整个 s1 和 s2。如果 s1 = “红蓝红红红黄”和 s2 = “ abbaac ”。在第三个red之后，基本上没有必要继续迭代它。

那么，关于如何做到这一点有更好的主意吗？

代码：

#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;
}
4

5 回答 5

2

@Tony 以同样的想法击败了我，但既然我已经输入了这个，那就这样吧:-)

首先，不要太在意效率，关注正确性：确实，过早的优化是万恶之源。编写测试用例并确保您的代码通过每一个。

其次，我想我会从地图/字典 D 开始，并有一个循环，我将在其中解析每个字符串的一个元素（s1 中的一个单词，我们称之为“w”和 s2 中的一个字符，说“ c")，选择一个元素作为键（比如“c”字符）并检查“c”是否已经在字典中有一个条目：

  • 如果我们同时用完了元素，则字符串匹配
  • 如果我们在一侧用完了元素，我们就知道没有匹配项
  • 如果“c”在 D 中没有条目，则存储当前值：D[c] = w;
  • 否则，如果 "c" 已经有一个条目，请检查该条目是否与在字符串中找到的值匹配：是 D[c] == w? 如果不是，我们就知道没有匹配

如果该代码有效，则可以开始优化。在您的示例中，也许我们可以使用简单的数组而不是字典，因为 ASCII 字符是一个小的有限集。

于 2013-03-06T02:59:32.987 回答
1

它不是最有效的代码，但接近于最简单的代码：

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
于 2013-03-06T02:52:24.563 回答
0

你不需要两个向量。

在处理第二个字符串时，将第一个模式的计数与第一个条目进行比较。如果匹配，则继续，否则停止。对第二个字符串中的其余模式重复此操作。

您不需要存储第二个字符串的模式计数。

于 2013-03-06T02:41:53.153 回答
0

基本上，您要检查序列是否遵循相同的顺序。您不必担心顺序实际上是什么：第一第二第一第三就足够了。现在，您可以使用以某种方式将字符串映射到 int 的容器来执行此操作。但是，您将存储每个字符串的副本，而忽略了您并不真正关心字符串值的事实。对于微小的测试用例，这无关紧要，但对于大量的长词，你会在不需要的时候快速消耗内存。

因此，让我们利用我们不关心字符串值或存储它们的事实。如果是这种情况，我们可以使用哈希函数将我们的字符串转换为简单的 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]

编辑：这是一个适用于 VS2010 的非 C++11 版本。但是，由于 C++03 在标准库中不包含字符串散列函数，因此该示例使用了从堆栈溢出中获取的散列函数。如果您可以访问 boost 库，则可以使用一个更好的哈希函数。

于 2013-03-06T03:17:01.197 回答
0

编辑

我刚刚读到这个问题有一个字符串中的模式，这个答案与比较不同类型的集合有关。如果首先转换了 2 个输入字符串，我想答案仍然存在一些问题 :)

我不会说这是最有效的解决方案，但我喜欢它的可扩展性。

首先，有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
};

请注意，这既快又脏，我相信它可以提高效率。

于 2013-03-06T21:08:29.763 回答