0

我将 3 个字符串传递给函数，并且需要查看字符串以找到出现在所有三个字符串中的单词。字符串只是没有空格或插符的字母。我编写了一个代码来遍历 2 个字符串，但由于某种原因它不起作用。任何帮助表示赞赏。

char* najduljiPodniz(char* niz1, char* niz2, char* niz3)
{
   int i,j,t1,br=0;

   for(i=0;i<strlen(niz1);i++)
   {
       for(j=0;j<strlen(niz2);j++)
       {
           if(niz1[i]==niz2[j])
           {
               t1=i;
               br++;
               while(niz1[i]==niz2[j])
               {
                   br++;
                   i++;
                   j++;
               }
           }
           else break;
       }
   }

char *podniz=(char*)malloc(sizeof(char)*br+1);

for(i=0,j=t1;j<br;i++,j++)
    podniz[i]=niz1[j];

for(i=0;i<br;i++)
    printf("%s",podniz[i]);

return 0;
}

为了澄清：字符串的示例是：“afsdmartiangknrhg”。所以，随机字母和字符串中的某处有一个实际的单词。在这个例子中是“火星人”。其他 2 个字符串也包含单词“martian”。martian 这个词对我来说是“未知的”，所以我无法检查字符串中的实际单词。

4

3 回答 3

1

好的，这是我根据修改后的问题描述的新答案（请参阅我的第一个答案的评论）。

首先，选择三个字符串中最短的一个。迭代该字符串的所有可能的子字符串，从最长的开始。对于每个子字符串，strstr用于在其他两个字符串中搜索它。如果在两者中都找到了，那么您就有了解决方案。

尝试类似：

for (i=0; i<N; i++) {
    for (j=0; j<=i; j++) {
        int tmp = a[N-1-i+j];
        a[N-1-i+j] = 0;
        if (strstr(b, a+j) && strstr(c, a+j)) printf("got '%s'\n", a+j);
        a[N-1-u+j] = tmp;
    }
}
于 2012-12-17T19:37:14.887 回答
0

显而易见的解决方案是从最短的字符串（以字数衡量）开始并遍历该字符串中的每个单词。对于每个单词，调用strstr以尝试在其他两个字符串中找到它，并进行一些额外的工作来检查它是否位于单词边界，如果发现它嵌入到更大的单词中，则继续搜索。

我想这有不错的表现；它是字符总数的二次方，但您可以更好地绑定它；它大致O(N*M)是N字符串中单词最少的单词M数和字符总数。（注意：我假设线性时间strstr，而不是二次算法之一。）

于 2012-12-17T18:08:13.637 回答
0

你在这里有两个问题。“为什么我的程序不起作用？” 和“我该如何解决这个问题？”

对于第一个问题，主要问题是您的内部 while 循环递增iand j，这意味着如果您在niz1and之间找到任何常见字符niz2，您将跳过外部循环中的以下字符并且永远不会查找包含它们的子字符串. 例如，如果niz1是 "afsdmartiangknrhg" 并且niz2在任何地方都包含一个 'd'，您将跳过 'martian' in 中的 'm' niz1，因此永远不会寻找匹配niz2

对于第二个问题，听起来您的问题简化为：给定一个字符串 x 和一组字符串 y_1..y_n，找到 x 的最长子字符串，它存在于所有 y_1..y_n 中。所以显而易见的解决方案变成：

  1. 选择最短的输入字符串并将其称为“x”。调用其余的 y_1..y_n。

  2. 对于 x 的每个子串，从最长到最短，检查它是否存在于所有 y_1..y_n 中。如果你找到一个，你就完成了。如果不是，请继续使用可能较短的子字符串

这将需要 O(n * k^2) 子字符串检查，其中 n 是字符串的数量，k 是最短的长度。每个子字符串检查本身可能需要 O(k) 时间，因此总体而言 O(n * k^3) - 相当慢，但如果你的最短字符串很短，可能没问题。

于 2012-12-17T19:40:19.170 回答