c - C语言求两个字符串中最长的公共(public)词？

Question

一段时间以来，我一直无法找到两个字符串中最长的常用词。首先我想到了用“isspace”函数来做这件事，但不知道如何找到一个常用词。然后我想到了“strcmp”，但到目前为止我只能比较两个字符串。我在想一些方法来合并 strcmp 和 isspace 以找到不同的单词，然后使用临时值找到最长的单词，但我想不出这样做的正确代码。

   #include <stdio.h>

   int strcmp(char s[],char t[]);


 void main()
 {

    char s[20],t[20];
   printf("Type in a string s.\n");
   gets(s);
    printf("Type in a string t.\n");
    gets( t );
   printf("The result of comparison=%d\n",strcmp(s,t));

    return 0;
      }


   int strcmp(char s[],char t[])
  {
   int i;
   for(i=0;s[i]==t[i];i++)
   if(s[i]=='\0')
   return( 0 );
   return(s[i]-t[i]);
   }

请帮我解决这个问题。欢迎和赞赏所有想法(和代码)。提前致谢!

编辑:

我已经为此苦苦挣扎了一段时间，我想我有解决方案，但这是一种非常严格的方法。该程序有一个错误，可能与数组“ptrArray1”有关，但我无法修复它。

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


     int returnArrayOfWords (char* str4Parsing, char* arrayParsed[])
       {
// returns the length of array
char seps[]   = " \t\n"; // separators
char *token = NULL;
char *next_token = NULL;
int i = 0;

// Establish string and get the first token:
token = strtok( str4Parsing, seps);

// While there are tokens in "str4Parsing"
while ((token != NULL))
{
    // Get next token:
    arrayParsed[i] = token;
    //printf( " %s\n", arrayParsed[i] );//to be commented
    token = strtok( NULL, seps);
    i++;
}
return i;
      }

      void printArr(char *arr[], int n)
     {
int i;
for ( i = 0; i < n; i++)
{
    printf("Element %d is %s \n", i, arr[i]);
}
   }


     void findLargestWord(char *ptrArray1[], int sizeArr1, char              *ptrArray2[], int sizeArr2)
{
int maxLength = 0;
char *wordMaxLength = NULL ;
int i = 0, j = 0;
char *w1 = NULL, *w2 = NULL; /*pointers*/
int currLength1 = 0, currLength2 = 0 ;

//printArr(&ptrArray1[0], sizeArr1);
//printArr(&ptrArray2[0], sizeArr2);

for (i = 0; i < sizeArr1; i++)
    {
    // to find the largest word in the array
    w1 = (ptrArray1[i]); // value of address (ptrArray1 + i)
    currLength1 = strlen(w1);
    //printf("The word from the first string is: %s and its length is : %d \n", w1, currLength1); // check point

    for (j = 0; j < sizeArr2; j++)
        {
        w2 = (ptrArray2[j]); // value of address (ptrArray2 + j)
        currLength2 = strlen(w2);
        //printf("The word from the second string is : %s and its length is : %d \n", w2, currLength2); // check point

        if (strcoll(w1, w2) == 0 && currLength1 == currLength2)
            // compares the strings
            {
            if (currLength2 >= maxLength)
                // in the variable maxLength -> the length of the longest word
                {
                    maxLength = currLength2;
                    wordMaxLength = w2;
                    printf("The largest word for now is : %s and its length is : %d \n", wordMaxLength, maxLength); // check point
                }
            }
        }
    }
printf("The largest word is: %s \n", wordMaxLength);
printf("Its length is: %d \n", maxLength);
    }



     int main ()
      {
int n = 80; /*max number of words in string*/
char arrS1[80], arrS2[80];
char *ptrArray1 = NULL, *ptrArray2 = NULL;
int sizeArr1 = 0, sizeArr2 = 0;

// to allocate memory:
ptrArray1 = (char*)calloc(80, sizeof(char));
if(ptrArray1 == NULL)
{
    printf("Error! Memory for Pointer 1 is not allocated.");
    exit(0);
}

ptrArray2 = (char*)calloc(80, sizeof(char));
if(ptrArray2 == NULL)
{
    printf("Error! Memory for Pointer 2 is not allocated.");
    exit(0);
}

printf("Type your first string: ");
fgets(arrS1, 80, stdin);
sizeArr1 = returnArrayOfWords (arrS1, &ptrArray1); // sizeArr1 = number of elements in array 1

printf("Type your second string: ");
fgets(arrS2, 80, stdin);
sizeArr2 = returnArrayOfWords (arrS2, &ptrArray2); // sizeArr2 = number of elements in array 2

findLargestWord(&ptrArray1, sizeArr1, &ptrArray2, sizeArr2);

free(ptrArray1);
free(ptrArray2);
return 0;
          }

我也尝试使用后两个已发布的解决方案，但我在使用它们时遇到了问题，如下所述。

欢迎对我的代码提供任何帮助，使用后一种解决方案解决我的问题或提出新的解决方案。提前谢谢大家!

附言。如果我的代码放置不当，我很抱歉。我仍然不太擅长使用展示位置。

Answer 1

有很多方法可以解决这个问题。下面，一个指向其中一个字符串中每个字符的指针用于使用 strchr 搜索另一个字符串中的匹配字符。找到匹配字符后，比较循环会运行，推进每个指针以设计存在的公共(public)子字符串的长度(如果有的话)。

例程，匹配字符，检查子串长度，重复，只要 strchr 返回一个有效指针就继续。每次找到更长的子串时，max 长度为返回而更新，并且使用 strncpy 和 nul-terminated 将存在的子字符串复制到 r，以便最长的公共(public)字符串的文本可用调用函数 main 在这里。

这是一种相当蛮力的方法，可能会有一些额外的调整来提高效率。函数本身是:

/** return length of longest common substring in 'a' and 'b'.
 *  by searching through each character in 'a' for each match
 *  in 'b' and comparing substrings present at each match. the
 *  size of the longest substring is returned, the test of the
 *  longest common substring is copied to 'r' and made available
 *  in the calling function. (the lengths should also be passed
 *  for validation, but that is left as an exercise)
 */
size_t maxspn (const char *a, const char *b, char *r)
{
    if (!a||!b||!*a||!*b) return 0; /* valdate parameters */

    char *ap = (char *)a;           /* pointer to a       */
    size_t max = 0;                 /* max substring char */

    for (; *ap; ap++) {             /* for each char in a */
        char *bp = (char *)b;       /* find match in b with strchr */
        for (; *bp && (bp = strchr (bp, *ap)); bp++) {
            char *spa = ap, *spb = bp; /* search ptr initialization */
            size_t len = 0;         /* find substring len */
            for (; *spa && *spb && *spa == *spb; spa++, spb++) len++;
            if (len > max) {        /* if max, copy to r  */
                strncpy (r, ap, (max = len));
                r[max] = 0;         /* nul-terminate r    */
            }
        }
    }

    return max;
}

返回长度max，然后在函数执行期间更新到r导致r保存与最长子串匹配关联的字符串.

其他改进是删除 gets，由于其安全风险，它在 C11 中被删除而没有弃用。它不应再被任何理智的编码人员使用(应该涵盖我们大约 40% 的人)。将剩余的位放在一起，一小部分测试代码可能是:

#include <stdio.h>
#include <string.h>

#define MAXC 128

size_t maxspn (const char *a, const char *b, char *r);
void rmlf (char *s);

int main (void) {

    char res[MAXC] = "", s[MAXC] = "", t[MAXC] = "";

    printf ("Type in a string 's': ");
    if (!fgets (s, MAXC, stdin)) {  /* validate 's' */
        fprintf (stderr, "error: invalid input for 's'.\n");
        return 1;
    }
    rmlf (s);   /* remove trailing newline */
    printf ("Type in a string 't': ");
    if (!fgets (t, MAXC, stdin)) {  /* validate 't' */
        fprintf (stderr, "error: invalid input for 's'.\n");
        return 1;
    }
    rmlf (t);   /* remove trailing newline */

    /* obtain longest commons substring between 's' and 't' */
    printf ("\nThe longest common string is : %zu ('%s')\n",
            maxspn (s, t, res), res);

    return 0;
}

/** return length of longest common substring in 'a' and 'b'.
 *  by searching through each character in 'a' for each match
 *  in 'b' and comparing substrings present at each match. the
 *  size of the longest substring is returned, the test of the
 *  longest common substring is copied to 'r' and made available
 *  in the calling function. (the lengths should also be passed
 *  for validation, but that is left as an exercise)
 */
size_t maxspn (const char *a, const char *b, char *r)
{
    if (!a||!b||!*a||!*b) return 0; /* valdate parameters */

    char *ap = (char *)a;           /* pointer to a       */
    size_t max = 0;                 /* max substring char */

    for (; *ap; ap++) {             /* for each char in a */
        char *bp = (char *)b;       /* find match in b with strchr */
        for (; *bp && (bp = strchr (bp, *ap)); bp++) {
            char *spa = ap, *spb = bp;
            size_t len = 0;         /* find substring len */
            for (; *spa && *spb && *spa == *spb; spa++, spb++) len++;
            if (len > max) {        /* if max, copy to r  */
                strncpy (r, ap, (max = len));
                r[max] = 0;         /* nul-terminate r    */
            }
        }
    }

    return max;
}

/** remove trailing newline from 's'. */
void rmlf (char *s)
{
    if (!s || !*s) return;
    for (; *s && *s != '\n'; s++) {}
    *s = 0;
}

示例使用/输出

$ ./bin/strspn
Type in a string 's': a string with colors123456789 all blue
Type in a string 't': a string without colors1234567890 all red

The longest common string is : 16 (' colors123456789')

或者，另一个可能更容易形象化的:

$ ./bin/strspn
Type in a string 's': green eel
Type in a string 't': cold blue steel

The longest common string is : 3 ('eel')

查看代码并与其他答案进行比较。如果您有任何其他问题，请告诉我。还应添加一些其他验证，以确保文本不会超出缓冲区的末尾等。希望这会提供一些帮助或替代方法。

---

额外的子串

为了确保您和我看到的是同一件事，我在下面提供了更多使用示例。没有错误，代码按预期执行。如果您在修改代码时遇到问题，请告诉我您正在尝试做什么，我可以提供帮助。我上面代码中的每个指针增量都经过验证。如果您更改有关指针增量或nul-termination 的任何内容，除非您也考虑到验证中的更改，否则代码将无法工作。

$ ./bin/strspn
Type in a string 's': 1
Type in a string 't':

The longest common string is : 0 ('')

$ ./bin/strspn
Type in a string 's': A man a plan a canal panama
Type in a string 't': a man a plan a river panama

The longest common string is : 14 (' man a plan a ')

$ ./bin/strspn
Type in a string 's': this is my favorite string
Type in a string 't': this is my favoritist string

The longest common string is : 18 ('this is my favorit')

$ ./bin/strspn
Type in a string 's': not the same until here
Type in a string 't': cant be equal till here

The longest common string is : 6 ('l here')

$ ./bin/strspn
Type in a string 's': some str with ten in the middle
Type in a string 't': a string often ignorded

The longest common string is : 5 ('ten i')

---

最长的常用词

好的，在我终于明白你想要完成的事情之后，你可以在 's' 和 ' 这两个字符串之间选择最长的常用词 ' 通过使用 strtoktokenizing 每个字符串，将指向每个字符串中每个单词的指针保存在单独的指针数组中，然后简单地迭代指针数组以选择最长的常用词(如果有多个相同长度的常用词，则为第一个)。您只需要像下面这样简单的东西。

注意 strtok 修改字符串's' 和't'，所以如果你复制需要保留原件。

/** return length of longest common word in 'a' and 'b'.
 *  by tokenizing each word in 'a' & 'b' and iterating over
 *  each, returning the length of the logest match, and updating
 *  'r' to contain the longest common word.
 */
size_t maxspnwhole (char *a, char *b, char *r)
{
    if (!a||!b||!*a||!*b) return 0; /* valdate parameters */

    char *arra[MAXC] = {NULL}, *arrb[MAXC] = {NULL};
    char *ap = a, *bp = b;          /* pointers to a & b */
    char *delim = " .,-;\t\n";      /* word delimiters   */
    size_t i, j, len, max, na, nb;  /* len, max, n-words */
    len = max = na = nb = 0;

    /* tokenize both strings into pointer arrays */
    for (ap = strtok (a, delim); ap; ap = strtok (NULL, delim))
        arra[na++] = ap;

    for (bp = strtok (b, delim); bp; bp = strtok (NULL, delim))
        arrb[nb++] = bp;

    for (i = 0; i < na; i++)           /* select longest common word */
        for (j = 0; j < nb; j++)
            if (*arra[i] == *arrb[j])             /* 1st chars match */
                if (!strcmp (arra[i], arrb[j])) { /* check word      */
                    len = strlen (arra[i]);
                    if (len > max) {              /* if longest */
                        max = len;                /* update max */
                        strcpy (r, arra[i]);      /* copy to r  */
                    }
                }

    return max;
}

将它与其他代码集成，你可以比较这样的结果:

#include <stdio.h>
#include <string.h>

#define MAXC 128

size_t maxspn (const char *a, const char *b, char *r);
size_t maxspnwhole (char *a, char *b, char *r);
void rmlf (char *s);

int main (void) {

    char res[MAXC] = "", s[MAXC] = "", t[MAXC] = "";

    printf ("Type in a string 's': ");
    if (!fgets (s, MAXC, stdin)) {  /* validate 's' */
        fprintf (stderr, "error: invalid input for 's'.\n");
        return 1;
    }
    rmlf (s);   /* remove trailing newline */
    printf ("Type in a string 't': ");
    if (!fgets (t, MAXC, stdin)) {  /* validate 't' */
        fprintf (stderr, "error: invalid input for 's'.\n");
        return 1;
    }
    rmlf (t);   /* remove trailing newline */

    /* obtain longest commons substring between 's' and 't' */
    printf ("\nThe longest common string is : %zu ('%s')\n",
            maxspn (s, t, res), res);

    /* obtain longest commons word between 's' and 't' */
    printf ("\nThe longest common word is : %zu ('%s')\n",
            maxspnwhole (s, t, res), res);

    return 0;
}

/** return length of longest common word in 'a' and 'b'.
 *  by tokenizing each word in 'a' & 'b' and iterating over
 *  each, returning the length of the logest match, and updating
 *  'r' to contain the longest common word.
 */
size_t maxspnwhole (char *a, char *b, char *r)
{
    if (!a||!b||!*a||!*b) return 0; /* valdate parameters */

    char *arra[MAXC] = {NULL}, *arrb[MAXC] = {NULL};
    char *ap = a, *bp = b;          /* pointers to a & b */
    char *delim = " .,-;\t\n";      /* word delimiters   */
    size_t i, j, len, max, na, nb;  /* len, max, n-words */
    len = max = na = nb = 0;

    /* tokenize both strings into pointer arrays */
    for (ap = strtok (a, delim); ap; ap = strtok (NULL, delim))
        arra[na++] = ap;

    for (bp = strtok (b, delim); bp; bp = strtok (NULL, delim))
        arrb[nb++] = bp;

    for (i = 0; i < na; i++)
        for (j = 0; j < nb; j++)
            if (*arra[i] == *arrb[j])
                if (!strcmp (arra[i], arrb[j])) {
                    len = strlen (arra[i]);
                    if (len > max) {
                        max = len;
                        strcpy (r, arra[i]);
                    }
                }

    return max;
}

/** return length of longest common substring in 'a' and 'b'.
 *  by searching through each character in 'a' for each match
 *  in 'b' and comparing substrings present at each match. the
 *  size of the longest substring is returned, the test of the
 *  longest common substring is copied to 'r' and made available
 *  in the calling function. (the lengths should also be passed
 *  for validation, but that is left as an exercise)
 */
size_t maxspn (const char *a, const char *b, char *r)
{
    if (!a||!b||!*a||!*b) return 0; /* valdate parameters */

    char *ap = (char *)a;           /* pointer to a       */
    size_t max = 0;                 /* max substring char */

    for (; *ap; ap++) {             /* for each char in a */
        char *bp = (char *)b;       /* find match in b with strchr */
        for (; *bp && (bp = strchr (bp, *ap)); bp++) {
            char *spa = ap, *spb = bp;
            size_t len = 0;         /* find substring len */
            for (; *spa && *spb && *spa == *spb; spa++, spb++) len++;
            if (len > max) {        /* if max, copy to r  */
                strncpy (r, ap, (max = len));
                r[max] = 0;         /* nul-terminate r    */
            }
        }
    }

    return max;
}

/** remove trailing newline from 's'. */
void rmlf (char *s)
{
    if (!s || !*s) return;
    for (; *s && *s != '\n'; s++) {}
    *s = 0;
}

示例使用/输出

$ ./bin/strlongestcmn
Type in a string 's': I have a huge boat.
Type in a string 't': I have a small boat.

The longest common string is : 9 ('I have a ')

The longest common word is : 4 ('have')

仔细阅读，如果您还有其他问题，请告诉我。