-2

次のコードは、文字列 s2 の任意の文字が出現する文字列 s1 内の最初の位置を返します。その最悪の時間計算量は O(m+n) です。どのように？

#include<stdio.h> 

int any(char *s1, char *s2) 
{

    char array[256]; 

    int  i;
    if (s1 == NULL) {
        if (s2 == NULL) {
            return(0);
        } else {
            return(-1);
        }
    }

    for(i = 0; i < 256; i++) {
        array[i] = 0;
    }

    while(*s2 != '\0') {
        array[*s2] = 1;
        s2++;
    }

    i = 0;
    while(s1[i] != '\0') {
        if (array[s1[i]] == 1) {
            return(i);
        }
        i++;
    }
    return(-1);
}
4

1 に答える 1

4

これは 2 つのステップで行われます。

  1. サイズ 256 の配列 (入力文字列の有効な各文字を表す) を初期化し、 s2 ( n ) の各文字に対して、その文字が存在することを示すために、配列内の文字スポットを 1 としてマークします。

  2. s1 内の文字 (0 からm まで) を反復処理し、配列内の各文字位置をチェックして、2 番目の文字列にあることを示す "present" (1) に設定されているかどうかを確認します。存在する場合は、s1 内のその文字のインデックスを返します。s1 の文字が s2 に存在しない場合 ( mで発見)、-1 を返します。

ステップ 1 は常にn (s2 の長さ)、ステップ 2 はm (s1 の長さ) までかかるため、最悪のケースは O(m+n) であり、一致がない場合、またはs1 の最後の文字のみが s2 に存在します。

于 2012-08-27T15:51:32.103 に答える