因此,给定一个最多7个字母的字符串,我需要找到该字符串的每个排列(包括所有字母和不包括所有字母),然后判断这些排列是否可以在我的字典中找到.txt文件,并打印匹配的.因此,基本上,如果用户输入"try",排列将是try、tr、tyr、ty、t、rty等,然后判断它们是否与txt文件中的单词匹配.我try 使用strncopy和strcmp来实现这一点,但程序并不总是正确地推断出两件事是相等的,它需要永远运行,并且有一个错误,它将零个字母作为原始字符串的排列.

这是我的代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 100 /* number of words in dictionary.txt */
#define MAX 7 /* max number of letters in given string */
 
/* function to swap values at two pointers */
void swap(char *x, char *y){
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}
 
/* function to find permutations of the string */
void permute(char *letters, int l, int r){

    if (l == r){

        char *a[SIZE];

        FILE *file = fopen("dictionary.txt", "r");

        char target[MAX_2];
        memset(target, '\0', sizeof(target));
    
        for (int i = 0; i < SIZE; i++){
            a[i] = malloc(100000);
            fscanf(file, "%s", a[i]);
        }

        for (int i = 0; i < 10; i++){
            for (int j = 0; j < r - 1; j++){
                strcpy(target, a[i]);
                if (strcmp(target, &letters[i]) == 0){
                    printf("%s\n", target);
                    printf("%s\n", letters);
                    printf("Match\n");
                }
                /*else if (strcmp(target, &letters[i]) != 0){
                    printf("%s\n", target);
                    printf("%s\n", letters);
                    printf("Not a match\n");
                }
                */
            }
        }
           
        for (int i = 0; i < SIZE; i++){
            free (a[i]);
        }

        fclose(file);
        
    }
    else{
        for (int i = l; i <= r; i++){
            swap((tiles+l), (tiles+i));
            permute(tiles, l+1, r);
            swap((tiles+l), (tiles+i));
        }
    }
}


int main(){

    /* initializing tile input */
    char letters[MAX];

    printf("Please enter your letters: ");
    scanf("%s", letters);

    /* finding size of input */
    int size = strlen(letters);

    /* finds all the permutation of the input */
    /* parameters: string; start of the string; end of the string */
    permute(letters, 0, size);
    
    return 0;
}

如果您能提供任何帮助或建议来查明我做错了什么,我们将不胜感激.

推荐答案

正如我在 comments 中所暗示的,只需将足够大的无符号整数的位用作位集,就可以将字符串的所有排列映射到单个代码值.因此,例如单词"try"的(相同长度)排列都映射到相同的值.

就我理解你的问题而言,你还需要匹配单词,这些单词从通缉单词的子字符串开始.为了实现这一点,你需要生成N个这样的代码,如果N是字母数,那么一个单词包含.例如,对于三个字母的单词,第一个字母的代码、前两个字母的代码以及所有三个字母的代码.

由于从文件中读取可能不是问题,下面是代码,展示了"基于代码"的字符串匹配思想(应该相当快):

#include <stdio.h>
#include <inttypes.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_WORD_LENGTH 7

typedef uint32_t WordCode;

typedef struct WordCodes_tag {
  size_t count;
  WordCode codes[MAX_WORD_LENGTH];
} WordCodes_t;

bool word_to_code(const char* word,
          size_t start,
          size_t end,
          WordCode* code) {
  if ((end - start) > MAX_WORD_LENGTH)
    return false;
  *code = 0;
  for (size_t i = start; i < end; i++) {
    char c = word[i];
    if ((c >= 'a') && (c <= 'z')) {
      char bit = c - 'a';
      WordCode mask = 1 << bit;
      (*code) |= mask;
    } else {
      return false;
    }
  }
  
  return true;
}

bool word_to_codes(const char* word, WordCodes_t* codes) {
  if (NULL == codes)
    return false;
  if (NULL == word)
    return false;
  codes->count = 0;
  size_t nchars = strlen(word);
  if (nchars > MAX_WORD_LENGTH)
    return false;
  for (size_t len = nchars; len >= 1; len--) {
    WordCode word_code;
    if (word_to_code(word, 0, len, &word_code)) {
      codes->codes[codes->count] = word_code;
      codes->count++;
    } else {
      return false;
    }
  }
  return true;
}

void show_word_codes(const WordCodes_t* codes) {
  if (NULL == codes) return;
  printf("(");
  for (size_t i = 0; i < codes->count; i++) {
    if (i > 0)
      printf(", %d", codes->codes[i]);
    else
      printf("%d", codes->codes[i]);
  }
  printf(")\n");
}

bool is_match(const WordCodes_t* a, const WordCodes_t* b) {
  if ((NULL == a) || (NULL == b))
    return false;
  if ((0 == a->count) || (0 == b->count))
    return false;
  const WordCodes_t *temp = NULL;
  if (a->count < b->count) {
    temp = a;
    a = b;
    b = temp;
  }
  size_t a_offset = a->count - b->count;
  for (size_t i = a_offset, j = 0; i < a->count; i++, j++) {
    if (a->codes[i] == b->codes[j])
      return true;
  }
  return false;
}

int main(int argc, const char* argv[]) {
  const char* wanted = "try";
  const char* dictionary[] = {
    "house", "mouse", "cat", "tree", "try", "yrt", "t"
  };
  size_t dict_len = sizeof(dictionary) / sizeof(char*);
  WordCodes_t wanted_codes;
  if (word_to_codes(wanted, &wanted_codes)) {
    printf("word codes of the wanted word '%s': ", wanted);
    show_word_codes(&wanted_codes);
    for (size_t i = 0; i < dict_len; i++) {
      WordCodes_t found_codes;
      if (word_to_codes(dictionary[i],&found_codes)) {
        printf("word codes of dictionary word '%s' (%s): ",
           dictionary[i],
           is_match(&wanted_codes, &found_codes) ?
           "match" : "no match");
        show_word_codes(&found_codes);
      } else {
        printf("word_to_codes(%s) failed!", dictionary[i]);
      }
    }
  } else {
    puts("word_to_codes() failed!");
    return -1;
  }
}

正如上面的函数is_match()所示,您只需要比较相应子字符串长度的代码.因此,即使你有两组最多7个数字,你也只需要最多7个比较.

输出如下(这似乎有道理):

./search
word codes of the wanted word 'try': (17432576, 655360, 524288)
word codes of dictionary word 'house' (no match): (1327248, 1327232, 1065088, 16512, 128)
word codes of dictionary word 'mouse' (no match): (1331216, 1331200, 1069056, 20480, 4096)
word codes of dictionary word 'cat' (no match): (524293, 5, 4)
word codes of dictionary word 'tree' (match): (655392, 655376, 655360, 524288)
word codes of dictionary word 'try' (match): (17432576, 655360, 524288)
word codes of dictionary word 'yrt' (match): (17432576, 16908288, 16777216)
word codes of dictionary word 't' (match): (524288)

C++相关问答推荐

如何知道我是否从非阻塞套接字读取所有内容

如果dim指定数组中的数据量,使用dim-1会不会潜在地导致丢失一个元素?

struct -未知大小

在创建动态泛型数组时,通过realloc对故障进行分段

有什么方法可以将字符串与我们 Select 的子字符串分开吗?喜欢:SIN(LOG(10))

可变宏不能编译

在C++中允许使用字符作为宏参数

为什么电路板被循环删除?

用C++高效解析HTTP请求的方法

在运行时判断C/C++指针是否指向只读内存(在Linux操作系统中)

如何摆脱-WIMPLICIT-Function-声明

GETS()在C++中重复它前面的行

如何使用WRITE()以指针地址的十六进制形式写入标准输出

在NASM中链接Linux共享库时出错-';将R_ X86_64_;foo';

execve 不给出which命令的输出

根据输入/输出将 C 编译过程分为预处理、编译、汇编和链接步骤

GDB 用内容初始化数组

获取指向 struct 的指针而不显式传递它

解释 printf("%# 01.1g",9.8) 中的格式说明符

在内存泄漏中获取Syscall param execve(argv) 指向未初始化的字节?