c++ - 查找其字符可能有多个变体的字符串的所有可能版本

Question

我正在寻找一些关于如何找到其字符可能有多个变体的字符串的所有可能版本的提示。

一个简单的例子: “澳门”是起始字符串。字符“a”有变体“ä”，字符“o”有变体“ö”。

目标是从上面的信息中得到如下列表:

Macao
Mäcao
Macäo
Mäcäo
Macaö
Mäcaö
Macäö
Mäcäö

到目前为止，我的方法是识别和提取具有变体的字符以简化操作。这个想法是处理各个字符而不是整个单词。

aao
äao
aäo
ääo
aaö
äaö
aäö
ääö

以下代码查找我们正在使用的变体。

std::vector<std::string> variants;
variants.push_back("aä");
variants.push_back("oö");

std::string word = "Macao";
std::vector<std::string> results;
for (auto &variant : variants) {
    for (auto &character : word) {
        if (variant.front() == character) {
            results.push_back(variant);
        }
    }
}

std::cout << "The following characters have variants: ";
for (auto &i : results) {
    std::cout << i.front();
}
std::cout << std::endl;

下一步是找到各个字符的所有可能组合。为此，我写了下面的函数。它根据 results 中每个字符串的第一个字符创建一个新字符串。

std::string read_results(std::vector<std::string> &results)
{
    std::string s;
    for (auto &c : results) {
        s.push_back(c.front());
    }
    return s;
}

我的想法是，然后更改存储在 results 中的字符串，以获得所有可能的组合，这就是我遇到的问题。我注意到 std::rotate 似乎会有帮助。

Answer 1

倒排索引可能会有用。

您可以将具有多个变体的所有字母按顺序存储在一个 vector 中，并为每个字母创建一个具有分组索引的 vector ，以便第 i 个字母属于组 I[i]，所有索引与 I[i] 相同的字母都是同一字母的变体:

string L = "aoäöâô"; // disclaimer: i don't know if this is really in order
unsigned int I[]  = {0,1,0,1,0,1};
// this means that "aäâ" belong to group 0, and "oöô" belong to group 1

你可以为前面的 L 和 I 建立倒排索引，像这样:

vector<vector<unsigned int> > groups;
// groups[k] stores the indices in L of the letters that belongs to the k-th group.
// do groups.reserve to make this operation more efficient
for(size_t i = 0; i < L.size(); ++i)
{
  unsigned int idx = I[i];
  if(idx <= groups.size()) groups.resize(idx+1);
  groups[idx].push_back(i);
}

L 中的字母按顺序排列很重要，因此您稍后可以对其进行二进制搜索，这需要 O(logn) 而不是 通常循环的 O(n)。然后，一旦你有了你的字母组，你就可以用倒排索引找到它的变体:

char letter = 'a';
string::iterator it = std::lower_bound(L.begin(), L.end(), letter);
if(it != L.end() && *it == letter)
{
  unsigned int idx = I[ it - L.begin() ];
  // the letter has variants because it belongs to group idx
  const vector<unsigned int>& group = groups[idx];
  for(vector<unsigned int>::const_iterator git = group.begin();
    git != group.end(); ++git)
  {
    // now, L[*git] is one of the variants of letter
    ...
  }
}