文字列１から文字列２を検索するプログラム＋解説

strstrっていう関数がある

#include <string.h>
char *strstr(const char *s1, const char *s2);

これを学習目的で自作する人が居たので、類似のソースを見つけて解説してみた
printfで出力の途中経過を混ぜてます

ソース

#include <stdio.h>

char *myStrstr(const char *s1, const char *s2)
{
    printf("start\n");
    const char *p1 = s1;
    const char *p2 = s2;
    
    while (*p1 && *p2) {
        if (*p1 == *p2) {
            p1++;
            p2++;
            printf("true [p1:%s] [p2:%s]\n",p1,p2);
        } else {
            long diff = (p2-s2-1);
            p1 -= p2 - s2 - 1;
            p2 = s2;
            printf("false [p1:%s] [p2:%s] ",p1,p2);
            printf("p1 pointer moves %ld\n",diff);
        }
    }
    printf("end\n");
    printf("p2 is [%s], [%s] - ([%s] - [%s]) = [%s]\n",p2,p1,p2,s2,(p1 - (p2 - s2)));
    return (*p2 ? NULL : (char *)(p1 - (p2 - s2)));
}

int main(void){
    const char* str1 = "eyanyaoewar9nyan349reawr";
    const char* str2 = "nyan";
    
    char* str3 = myStrstr(str1,str2);
    
    printf("result is %s",str3); 
}

str1を「eyanyaoewar9nyan349reawr」
str2を「nyan」とした。

出力結果

start
false [p1:yanyaoewar9nyan349reawr] [p2:nyan] p1 pointer moves -1
false [p1:anyaoewar9nyan349reawr] [p2:nyan] p1 pointer moves -1
false [p1:nyaoewar9nyan349reawr] [p2:nyan] p1 pointer moves -1
true [p1:yaoewar9nyan349reawr] [p2:yan]
true [p1:aoewar9nyan349reawr] [p2:an]
true [p1:oewar9nyan349reawr] [p2:n]
false [p1:yaoewar9nyan349reawr] [p2:nyan] p1 pointer moves 2
false [p1:aoewar9nyan349reawr] [p2:nyan] p1 pointer moves -1
false [p1:oewar9nyan349reawr] [p2:nyan] p1 pointer moves -1
false [p1:ewar9nyan349reawr] [p2:nyan] p1 pointer moves -1
false [p1:war9nyan349reawr] [p2:nyan] p1 pointer moves -1
false [p1:ar9nyan349reawr] [p2:nyan] p1 pointer moves -1
false [p1:r9nyan349reawr] [p2:nyan] p1 pointer moves -1
false [p1:9nyan349reawr] [p2:nyan] p1 pointer moves -1
false [p1:nyan349reawr] [p2:nyan] p1 pointer moves -1
true [p1:yan349reawr] [p2:yan]
true [p1:an349reawr] [p2:an]
true [p1:n349reawr] [p2:n]
true [p1:349reawr] [p2:]
end
p2 is [], [349reawr] - ([] - [nyan]) = [nyan349reawr]
result is nyan349reawr

解説

p1のp2の1文字目を比較して

• 一致したら次の文字を比較、すなわち先頭文字を削る（p1++;p2++;）…①
• 一致しなかったらp1のポインタの位置をp2-s2-1分移動し、(p1 -= p2 - s2 - 1;)し、p2の文字列を元に戻す(p2=s2;)…②

p2-s2-1分、ポインタを移動するというのは、
①でp1を何度インクリメントしたかで結果が変わる

• 0回なら1個左に移動
• 1回なら移動しない
• 2回なら1個右に移動
• 3回なら2個右に移動

って感じ

そのとき、p1の文字列の状態は、
ポインタが、

• 1個左に移動したら、p1から1文字を削除
• 移動しないなら、p1を変更しない
• 1個右に移動したら、p1を1文字復元
• 2個右に移動したら、p1を2文字復元

って感じ

ループは、以下の条件を満たすまで回り続ける。

• ①が呼ばれることでp2のポインタが文字列外へ移動するか
• ②が呼ばれることでp1のポインタが文字列外へ移動するか

戻り値は、
p2のポインタの先頭が

• 存在すれば、NULL
• 存在しなければ、p2と一致した位置のp1のポインタ

を返す。