没有得到预期的输出 - 查找一个词的所有子词

Question

我正在编写代码来查找给定单词的所有子词。它接受一个 WordGame，它的结构中有一个字典（使用树实现）。

它应该产生的是一个词的所有子词，这些子词在我前面提到的字典中。但是，例如单词是 "libels"，输出是

"lib"

"libel"

"libels"

"libs"

密码是

void swap (char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

void subWords(char *a, int i, int n, WordGame game) 
{

//This algorithm first finds all the anagrams of a 6 letter word.
//For each anagram it then finds all the 3/4/5/6 in the dicitonary.
//To find the 3/4/5/6 letter words it first finds all the 3 letter words
//then the 4 letter words and so on. 
//For example, to find 3 letter words from the word ABCDEF it does this
//  A   B   C   D   E   F 
// |_| |_| |_|             = ABC

// A    B   C   D   E   F
//     |_| |_| |_|         = BCD 

//etc

//Since it does this for all the anagrams of the 6 letter word it should
//find all the 3 letter subwords of the 6 letter word then for the 4 letter
//subwords and so on.

   int j; 
   int k;
   int m;
   if (i == n){ //When an anagram is foumd
    for(k = 3; k <= 6; k++){ //Used for finding subwords of lengths 3-6
        char str[k];
        for(m = 0; m + k <= 6; m++){  //Used for making sure we don't step
            strncpy(str,a+m,k);       //out of array and moving along array
            str[k] = '[=11=]';
            if(DictFindWord(game->dict,str) !=0){ 
                if(ListSearch(game->aWords[k],str) == NULL){
                    ListInsertInOrder(game->aWords[k],str);
                    printf("%s\n",str);
                }
            }                     
        }
    }
   }

   else
   {
        for (j = i; j <= n; j++)
       {
          swap((a+i), (a+j));
          subWords(a, i+1, n, game);
          swap((a+i), (a+j)); 
       }
   }
}

它似乎找到了单词初始状态的子词，即 l-i-b-e-l-s。它没有找到胆汁，因为它不在单词的初始状态，我的代码应该找到所有字谜的子词，但似乎没有找到单词的排列。这使得我的 subWord 函数看起来没有生成初始单词的字谜，但这不是真的，因为当我运行我的代码是这样的：

   int j; 
   if (i == n){ //When an anagram is foumd
   printf("%s\n",a);
   }

   else
   {
        for (j = i; j <= n; j++)
       {
          swap((a+i), (a+j));
          subWords(a, i+1, n, game);
          swap((a+i), (a+j)); 
       }
   }
}

它打印单词所有可能的排列。函数 ListSearch、InsertInOrder 是提供的函数，很可能是正确的。

注意：当我调用函数时，我调用函数 subWords，我用比数组大小小一的 n 调用它，所以我不会访问数组外的元素。

Answer 1

您的代码中有一些越界访问。

首先，您的 "raw" 版本仅打印排列，对我不起作用，因为您访问元素 a[n]。数组索引包括 0，但不包括数组长度。循环如：

for (j = i; j <= n; j++) ...

其中 j 用于索引长度为 n 的数组应该敲响警钟。所以：

} else {
    for (j = i; j < n; j++) {
        swap((a + i), (a + j));
        subWords(a, i + 1, n);
        swap((a + i), (a + j));
    }
}

你的辅助数组也是如此str。它包含 k 个字符加上末尾的空终止符。您使用

正确设置了空终止符

str[k] = '[=12=]';

但要使其工作，char 数组 str 必须比 k 多一个元素，否则您访问数组末尾后的元素：

char str[k + 1];

(算法本身效率很低。对于 "libels"，你最终生成 6!= 720 个排列，然后为每个排列检查所有 4 + 3 + 2 + 1 = 10 个子词。你最终多检查一些单词，不仅仅是因为你的单词有两个 L。

您可以通过先找到原始字符串的子字符串然后对子字符串进行置换来减少检查次数。如果原始单词具有唯一字母，这至少可以保证您不会对一个单词进行多次检查。对于诽谤，这会将您的支票减少到 4·3！ + 3·4！ + 2·5！ + 1·6！ = 1054 张支票。

如果你必须在同一个词典中检查很多单词，即使这样也会很慢。如果你能以一种可以快速找到所有可以由 1b、1 e、1 i、2 l's 和 1 s 组成的单词的方式存储你的字典，你就可以加快你的算法。）

没有得到预期的输出 - 查找一个词的所有子词

Not getting expected output - Finding all subwords of a word

c

debugging