0

関数に 3 つの文字列を渡します。文字列を調べて、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

OK、これが問題の改訂された説明に基づく私の新しい回答です（私の最初の回答のコメントを参照してください）。

まず、3 つの文字列のうち、最も短い文字列を選択します。最長のものから始めて、この文字列のすべての可能な部分文字列を反復処理します。部分文字列ごとstrstrに、他の 2 つの文字列で検索するために使用します。両方で見つかった場合は、解決策があります。

次のようなものを試してください：

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て他の両方の文字列で検索を試みます。単語の境界にあることを確認し、より大きな単語に埋め込まれていることがわかった場合は、検索を再開します。

これはまともなパフォーマンスだと思います。文字の総数は2次式ですが、それよりもうまくバインドできます。これは、文字列内で単語が最も少ない単語の数O(N*M)であり、文字の総数です。（注：2次アルゴリズムの1つではなく、線形時間を想定しています。）NMstrstr

于 2012-12-17T18:08:13.637 に答える
0

ここで 2 つの質問があります。「なぜ私のプログラムは動かないのですか？」「どうすればこの問題を解決できますか?」

最初の質問の主な問題は、内側の while ループがiとをインクリメントすることです。これは、 と の間にj共通の文字が見つかった場合、外側のループで次の文字をスキップし、それらを含む部分文字列を決して検索しないことを意味します。 . たとえば、「afsdmartiangknrhg」でどこかに「d」が含まれている場合、「martian」の「m」をスキップするため、その部分文字列に一致するように見えませんniz1niz2niz1niz2niz1niz2

2 番目の質問については、問題が次のように縮小されるように聞こえます。したがって、明らかな解決策は次のようになります。

  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 に答える