查找两个字符串之间的共同单词

Question

如何比较并查找两个标记化单词字符串之间的共同单词？

请帮我找到新的解决方案。

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define MAX 25

void findSame(char *str1, char *str2) {
    char *word1 = strtok(str1, " ");
    
    while(word1 != NULL){
        char *word2 = strtok(str2, " ");
        
        while(word2 != NULL){
            if(strcmp(word1,word2)==0){
                printf("%s ", word1);
                break;
            }
            word2 = strtok(NULL, " ");
        }
        word1 = strtok(NULL, " ");
        
    }
}

int main() {

    char str1[MAX], str2[MAX];
    int i;

    printf("Enter String 1: ");
    gets(str1);
    
    printf("Enter String 2: ");
    gets(str2);
    
    strlwr(str1); //convert strings to lowercase
    strlwr(str2); //convert strings to lowercase
    
    printf("\nOutput:\n");
    findSame(str1, str2);
    
    return 0;
}

程序应该如下所示：

输入字符串 1：快速的棕色狐狸跳过懒惰的狗

输入字符串 2：嘿，快点，棕色的猫和狗

输出： 快的棕色狗

Answer 1

代码存在问题，包括：

缓冲区溢出

"The quick Brown FOX jumped over the LAzy dog"

需要至少 46 个字节才能存储为 string，并且

str1[MAX]

的大小为 25。

• 使用

  gets()

  删除。自 2011 年以来，它不再是标准 C 库的一部分。

• 使用

  fgets()

  并去掉尾随的

  '\n'

  。

• 使用更宽的缓冲区。

• 测试用户是否尝试输入大量内容。

// Candidate helper function
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Candidate helper function
char *read_line(const char *prompt, size_t sz, char dest[sz]) {
  if (prompt) {
    fputs(prompt, stdout);
  }
  if (fgets(dest, (int) sz, stdin) ==  NULL) {
    perror("No input");
    exit (EXIT_FAILURE);
  }
  dest[strcspn(dest, "\n")] = '\0';  // Lop off potential trailing \n
  if (strlen(dest) + 1 >= sz) {
    perror("input too long");
    exit (EXIT_FAILURE);
  }
  return dest;
}
// To do: amend to flush input and re-prompt when input too long.


...
    // Sample usage

    //char str1[MAX], str2[MAX];
    //printf("Enter String 1: ");
    //gets(str1);
    //printf("Enter String 2: ");
    //gets(str2);

    #define LINE_MAX 100
    char str1[LINE_MAX + 1 + 1]; // 1 more for too long an input test, 1 more for \0
    read_line("Enter String 1: ", sizeof str1, str1);
    char str2[LINE_MAX + 1 + 1];
    read_line("Enter String 2: ", sizeof str1, str1);

修复“word”比较循环

留给其他人（或以后）。

Answer 2

一些问题...

1. 永远不要使用

   gets

   ——它是不安全的，因为它会在没有意识到的情况下溢出缓冲区。始终使用

   fgets

   代替。请参阅：为什么 gets 函数如此危险以至于不应该使用它？

2. MAX

   太小，无法包含示例输入字符串。

   gets

   will 溢出缓冲区，导致 UB（未定义行为）。
3. 在

   findSame

   中，在str1的

   first

   循环迭代之后，str2的

   inner

   循环已经分割了令牌。因此，在第二次迭代中，

   word2

   此后将永远为

   NULL

   。
4. 我们必须拆分[标记化]字符串并将其保存到

   char *

   数组中。然后，我们迭代这些字符串列表。

---

这是更正后的代码。注释如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <termios.h>

// NOTE/BUG: this is much too small for the input strings
#if 0
#define MAX 25
#else
#define MAX 250
#endif

// splitup -- split up a buffer into tokens
void
splitup(char **list,char *buf)
{
    size_t count = 0;

    // NOTE: this _is_ destructive of the original string

    char *cp = strtok(buf," ");

    while (cp != NULL) {
        if (count >= (MAX - 1))
            exit(2);

        list[count++] = cp;
        list[count] = NULL;

        cp = strtok(NULL," ");
    }
}

void
findSame(const char *str1, const char *str2)
{

    char *list1[MAX];
    char tmp1[MAX];

    // preserve original string
    strcpy(tmp1,str1);

    // split up string
    // split the first string into tokens
    splitup(list1,tmp1);

    char *list2[MAX];
    char buf2[MAX];

    // preserve original string
    strcpy(buf2,str1);

    // split the second string into tokens
    splitup(list2,buf2);

    for (char **word1 = list1;  *word1 != NULL;  ++word1) {
        for (char **word2 = list2;  *word2 != NULL;  ++word2) {
            if (strcmp(*word1, *word2) == 0) {
                printf("%s ", *word1);
                break;
            }
        }
    }

    printf("\n");
}

void
prompt(char *buf,size_t size,const char *str)
{

    printf("%s: ",str);
    fflush(stdout);

    // safe replacement for gets
    char *cp = fgets(buf,size,stdin);
    if (cp == NULL)
        exit(1);

    // just a nicety for debugging ...
    // pretty print if stdin redirected from file
    struct termios tio;
    if (tcgetattr(fileno(stdin),&tio) < 0)
        fputs(buf,stdout);

    // strip the newline
    cp = strchr(buf,'\n');
    if (cp != NULL)
        *cp = 0;

    // lowercase the string
    for (;  *buf != 0;  ++buf)
        *buf = tolower((unsigned char) *buf);
}

int
main(void)
{

    char str1[MAX], str2[MAX];

    prompt(str1,sizeof(str1),"Enter string 1");
    prompt(str2,sizeof(str2),"Enter string 2");

    printf("\nOutput:\n");
    findSame(str1, str2);

    return 0;
}

---

这是实际的程序输出：

Enter string 1: The quick Brown FOX jumped over the LAzy dog
Enter string 2: Hey Quick brown cat and dog

Output:
the quick brown fox jumped over the lazy dog