一种可能的算法，用于确定两个字符串是否是彼此的字谜？

我有这个想法（使用C语言）来检查由ASCII字母组成的两个字符串是否是彼此的字谜：

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

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

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

我相信如果所有三个都是正确的，那么字符串必须是彼此的字谜。 但是，我无法certificate这一点。 有人可以帮我certificate或反驳这会起作用吗？

谢谢！

Answer 1

我写了一个快速程序来强制搜索冲突，并发现这种方法并不总是有效。 字符串ABFN和AAHM具有相同的ASCII和和产品，但不是彼此的字母。 它们的ASCII总和为279，ASCII产品为23,423,400。

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

供参考，这是C ++源代码：

#include  #include  

希望这可以帮助！

Answer 2

你的做法是错误的; 我无法解释为什么因为我不理解它，但至少对于基数3有不同的集合具有相同的总和和产品： https ： //math.stackexchange.com/questions/38671/two-sets-的-3-正整数与-相等-相加和产品

Answer 3

字母az和AZ用于索引26个素数的数组，这些素数的乘积用作单词的哈希值。 同等产品< - >相同的字母。

（下面片段中primes26 []数组中散列值的顺序基于荷兰语中的字母频率，因为尝试最大限度地模拟了预期的产品）

 #include  #include  #include  #define COUNTOF(a) (sizeof (a)/ sizeof (a)[0]) typedef unsigned long long HashVal; HashVal hashmem (char *str, size_t len); unsigned char primes26[] = { 5,71,79,19,2,83,31,43,11,53,37,23,41,3,13,73,101,17,29,7,59,47,61,97,89,67, }; struct anahash { struct anahash *next; unsigned freq; HashVal hash; char word[1]; }; struct anahash *hashtab[1024*1024] = {NULL,}; struct anahash *new_word(char *str, size_t len); struct anahash **hash_find(struct anahash *wp); /*********************************************/ HashVal hashmem (char *str, size_t len) { size_t idx; HashVal val=1; if (!len) return 0; for (idx = 0; idx < len; idx++) { char ch = str[idx]; if (ch >= 'A' && ch <= 'Z' ) val *= primes26[ ch - 'A']; else if (ch >= 'a' && ch <= 'z' ) val *= primes26[ ch - 'a']; else continue; } return val; } struct anahash *new_word(char *str, size_t len) { struct anahash *wp; if (!len) len = strlen(str); wp = malloc(len + sizeof *wp ); wp->hash = hashmem(str, len); wp->next = NULL; wp->freq = 0; memcpy (wp->word, str, len); wp->word[len] = 0; return wp; } struct anahash **hash_find(struct anahash *wp) { unsigned slot; struct anahash **pp; slot = wp->hash % COUNTOF(hashtab); for (pp = &hashtab[slot]; *pp; pp= &(*pp)->next) { if ((*pp)->hash < wp->hash) continue; if (strcmp( wp->word, (*pp)->word ) > 0) continue; break; } return pp; } char buff [16*4096]; int main (void) { size_t pos,end; struct anahash *wp, **pp; HashVal val; memset(hashtab, 0, sizeof hashtab); while (fgets(buff, sizeof buff, stdin)) { for (pos=0; pos < sizeof buff && buff[pos]; ) { for(end = pos; end < sizeof buff && buff[end]; end++ ) { if (buff[end] < 'A' || buff[end] > 'z') break; if (buff[end] > 'Z' && buff[end] < 'a') break; } if (end > pos) { wp = new_word(buff+pos, end-pos); if (!wp) {pos=end; continue; } pp = hash_find(wp); if (!*pp) *pp = wp; else if ((*pp)->hash == wp->hash && !strcmp((*pp)->word , wp->word)) free(wp); else { wp->next = *pp; *pp = wp; } (*pp)->freq +=1; } pos = end; for(end = pos; end < sizeof buff && buff[end]; end++ ) { if (buff[end] >= 'A' && buff[end] <= 'Z') break; if (buff[end] >= 'z' && buff[end] <= 'a') break; } pos = end; } } for (pos = 0; pos < COUNTOF(hashtab); pos++) { if (! &hashtab[pos] ) continue; for (pp = &hashtab[pos]; wp = *pp; pp = &wp->next) { if (val != wp->hash) { fprintf (stdout, "\nSlot:%u:\n", pos ); val = wp->hash; } fprintf (stdout, "\t%llx:%u:%s\n", wp->hash, wp->freq, wp->word); } } return 0; } 

Answer 4

谢谢你这么好的问题！ 我没有试图完全反驳你的命题，而是花了一些时间试图找到增加它的方法，以便它成为现实。 我有一种感觉，如果标准偏差相等，那么两者是相等的。 但是，我没有测试那么远，而是做了一个更简单的测试，并且还没有找到一个反例。 这是我测试过的：

除了你之前提到的条件，

• 平方和的ASCII平方根必须相等：

我使用以下python程序。 我没有完整的证据，但也许我的回答会有所帮助。 无论如何，看看。

 from math import sqrt class Nothing: def equalString( self, strA, strB ): prodA, prodB = 1, 1 sumA, sumB = 0, 0 geoA, geoB = 0, 0 for a in strA: i = ord( a ) prodA *= i sumA += i geoA += ( i ** 2 ) geoA = sqrt( geoA ) for b in strB: i = ord( b ) prodB *= i sumB += i geoB += ( i ** 2 ) geoB = sqrt( geoB ) if prodA == prodB and sumA == sumB and geoA == geoB: return True else: return False def compareStrings( self ): first, last = ord( 'A' ), ord( 'z' ) for a in range( first, last + 1 ): for b in range( a, last + 1 ): for c in range( b, last + 1 ): for d in range( c, last + 1 ): strA = chr( a ) + chr( b ) + chr( c ) + chr( d ) strB = chr( d ) + chr( c ) + chr( b ) + chr( a ) if not self.equalString( strA, strB ): print "%s and %s should be equal.\n" % ( strA, strB ) print "Done" 

Answer 5

如果您不介意修改字符串，请对每个字符串进行排序并比较两个签名。