【ブラシノート】LeetCode_28:strStr()を実現_簡単(C)

テーマ:strStrを実現する()
haystack文字列とneedle文字列を指定し、haystack文字列にneedle文字列が現れる最初の位置(0から)を見つけます.存在しない場合は、-1を返します.
例1:
入力:haystack=「hello」、needle=「ll」出力:2
例2:
入力:haystack=「aaaa」、needle=「bba」出力:-1
この問題では、needleが空の文字列である場合、0を返します.これはC言語のstrstr()およびJavaのindexOf()定義と一致する.
この問題は見たばかりの頃は簡単だと思っていたが、意外にも穴が多かった.の自分で書いたコードは以下の通りですが、正しいかどうかはわかりませんが、どうせタイムアウトです...

int strStr(char * haystack, char * needle){

    char first;

    int i = 0;
    int j = 0;
    int k = 1;
    int length = strlen(haystack);
    int num = strlen(needle);
    int flag = 1;
    int judge = 0;
    int address;
    
    if(needle[0] == '\0') return 0;
    if(length < num) return -1;
    
    
        first = needle[0];

        while(haystack[i] != '\0')
        {
            if(haystack[i] == first)
            {
                address = i;
                for(j=i+1; k<num; j++)//   num   ok
                {
                    if(haystack[j] != needle[k])//     needle
                    {
                        flag = 0;
                        break;
                    }
                    k++;
                }
                if(!flag) //  break ，  haystack   needle       num   
                {
                    i = j-1;//     num   needle,    ，    i
                    k = 1;//  k=1
                    flag = 1;//  flag
                }
                else judge = 1;// break      needle
            }   
            i++; //  judge，       ， i++      1
        }

    if(!judge) return -1;
    else return address;
    
    

}

最初の構想は、haystackでスキャンしてneedleの頭文字を探し、見つからない場合は-1に戻ることです.見つけたら、その時の位置を記録し、スキャンし、次の文字がneedleの次の文字と同じであれば位置を返し、異なる場合はbreakがループし、-1を返します.
でも!この考えには抜け穴がある!!例:
入力:haystack=「missiissip」、needle=「issip」出力:5
この例では、needleの最初の文字は「i」なので、初めて現れた位置は1ですが、スキャンすると後ろの文字がneedleと合わないことがわかり、breakが出てきて-1に戻ります.これは間違っています!!あと一段あるので、またスキャン!!
だから私はまたjudge変数を設定して、breakが出てきたらi,j,flagの値を更新してスキャンして、次のhaystackの中でスキャンしていない文字がneedleに合っているかどうかを見ます.
でも!また問題が発生しました!!!最外層のwhileサイクルは最後にi++の動作があり、firstの位置を見つけることを制御する.しかしjudge=1の場合、firstが見つかった後、後ろの文字列がneedleと一致し、breakが値を更新してスキャンする必要がない場合、このときのiに1が加算され、addressもそれに応じて1が加算されます.だから私はi++をif(!judge)i++に変えましたが.タイムアウト...だから私は他の人のコードを見るしかありません..
以下は他人のコードを見て書いたACコードですが、n^2の複雑さは本当に遅いpで、振り返って大神の比較的速いアルゴリズムを見てみましょう.

int strStr(char * haystack, char * needle){

    int length = strlen(haystack);

    int num = strlen(needle);

    int flag = 0;

    int i,j;

    if(needle[0] == '\0') return 0;
    if(length <num) return -1;

    for(i=0; i<length; i++)
    {
        flag = 0;
        for(j=0; j<num; j++)
        {
            if(haystack[i+j] != needle[j])
            {
                flag = 1;
                break;
            }
        }
        if(!flag) return i;
    }
    return -1;

}

この二層サイクルの暴力解法は、外層サイクル制御haystack、内層サイクル制御needle、外層はi=0から、内層はj=0から、haystack[i+j]がneedle[j]と異なるとbreakし、その後、i++がneedleの最初の文字と同じ位置を見つけるまで、このように推す.次の点に注意してください.
1.flagの値は更新を忘れないでください!!前のmissiissipの例が現れる可能性があるので,1回以上の内層forサイクルに入る必要がある.
2.if(!flag) return i; この文は内層サイクルが終わった後、外層サイクル内に書きます.内層サイクルが終了した後、flag=0の場合、マッチングに成功したことを示すため、直接return;flag=1の場合,さらにスキャンマッチング操作が必要であることを示し,この判断を外層サイクルの外に書けば正解は得られない.外層サイクル終了の条件はhaystackがすべてスキャン終了したためflagの値は言いにくい.
3.hayaystack[i+j]の理解.内層サイクルが入るたびにjは0に初期化されるので、needleは毎回最初から比較され、私の最初のコードを省くたびに手動で更新されますが、haystackでneedleの最初の文字と同じ文字位置が見つからないと、内層サイクルを実行できません.入るとbreakが出るからです.見つけたら内層ループを実行すると、i+jの値はj++とともに増加し、haystackの最初の文字の出現位置でneedle文字列と比較し始め、私の前の「i=j-1」の愚かな更新操作を省くことに相当する.