小编典典

一种确定两个字符串是否互为字谜的可能算法?

algorithm

我有这个想法(使用C语言)来检查两个由ASCII字母组成的字符串是否彼此相同的字谜:

  1. 检查字符串长度是否相同。

  2. 检查两个字符串的所有字符的ASCII值之和是否相同。

  3. 检查两个字符串的所有字符的ASCII值的乘积是否相同。

我相信,如果所有这三个都是正确的,则字符串必须是彼此的字谜。但是,我无法证明这一点。有人可以帮助我证明或否认这可行吗?

谢谢!


阅读 287

收藏
2020-07-28

共1个答案

小编典典

我写了一个快速程序,强力搜索的冲突,并发现此方法确实
总是工作。字符串ABFN和AAHM具有相同的ASCII和和乘积,但不是彼此的字词。它们的ASCII总和为279,ASCII乘积为23,423,400。

冲突比这还多。我的程序搜索了所有长度为四的字符串,发现了11,737个冲突。

作为参考,这是C ++源代码:

#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;

int main() {
  /* Sparse 2D table where used[sum][prod] is either nothing or is a string
   * whose characters sum to "sum" and whose product is "prod".
   */
  map<int, map<int, string> > used;

  /* List of all usable characters in the string. */
  vector<char> usable;
  for (char ch = 'A'; ch <= 'Z'; ch++) {
    usable.push_back(ch);
  }
  for (char ch = 'a'; ch <= 'z'; ch++) {
    usable.push_back(ch);
  }

  /* Brute-force search over all possible length-four strings.  To avoid
   * iterating over anagrams, the search only explores strings whose letters
   * are in increasing ASCII order.
   */
  for (int a = 0; a < usable.size(); a++) {
    for (int b = a; b < usable.size(); b++) {
      for (int c = b; c < usable.size(); c++) {
        for (int d = c; d < usable.size(); d++) {
          /* Compute the sum and product. */
          int sum  = usable[a] + usable[b] + usable[c] + usable[d];
          int prod = usable[a] * usable[b] * usable[c] * usable[d];

          /* See if we have already seen this. */
          if (used.count(sum) &&
              used[sum].count(prod)) {
            cout << "Conflict found: " << usable[a] << usable[b] << usable[c] << usable[d] << " conflicts with " << used[sum][prod] << endl;
          }

          /* Update the table. */
          used[sum][prod] = string() + usable[a] + usable[b] + usable[c] + usable[d];
        }
      }
    }
  }
}

希望这可以帮助!

2020-07-28