//-----文字列検索システム-----

#include<iostream.h>

const int N1 = 301;

const int N2 = 21;

// 文字列の読みこみ

int mojiretu_no_yomikomi(char* p,int m)

{

        char c; // 文字の一時保存

        char gomibako; // '^'入力後の[return]をﾊﾞｯﾌｧから破棄するためのごみ箱

        int i;  // 入力された文字数

        cout << m << "文字以内のバイト文字(半角文字)を入力してください。\n"

                << "文字列の終わりは'^'を入力してください。\n"

                << "'^' は文字列に含まれません。\n"

                << "入力文字列 :";

        i=0;

        do

        {

                cin.get(c);

                *p = c;

                p++;

                i++;

        }while((c != '^') && (i < m));

        cin.get(gomibako);

        return (i-1);

}

// 文字列の検索(方法１)

int mojiretu_no_kennsaku_1(char* p1,char* p2,int n1,int n2)

{

        // n1:Text の文字数, n2:Pattern の文字数

        int i=0; // 照合中の Text の文字位置

        int j=0; // 照合中の Pattern の文字位置

        int k=0; // 文字照合回数

        int u;   // 一致した時の Pattern の先頭位置

        while(i < n1-n2+1) // 照合位置を文字列の左端から１個ずつずらしていく

        {

                while(j < n2) // Pattern の文字列との照合位置を左から１個ずつずらしていく

                {

                        k++; // 文字照合回数カウント

                        if(*(p1+i) != *(p2+j)) // 文字の照合

                                break;

                        else

                        {

                                i++;

                                j++;

                        }

                }

                if(j == n2)

                {

                        u = i-n2+1;

                        break;

                }

                else

                {

                    i = i-j+1;

                        j = 0;

                }

        }

        cout << "照合回数：" << k << "回 \n";

        return (u);

}

// 文字列の検索(方法２)

int mojiretu_no_kennsaku_2(char* p1,char* p2,int n1,int n2)

{

        // n1:Text の文字数, n2:Pattern の文字数

        int i = n2-1; // 照合中の Text の文字位置

        int j = n2-1; // 照合中の Pattern の文字位置

        int k = 0; // 文字比較回数

        int u;   // 一致した時の Pattern の先頭位置

        int ido_distance(char*,int,char); // 移動距離を求める関数

        while(i < n1) // 見つかるまで照合開始位置を右に移動させながら照合を繰り返す

        {

                while(j >= 0) // 文字列Pattern の右端の文字から１文字ずつ照合していく

                {

                        k++; // 文字照合回数カウント

                        if(*(p1+i) != *(p2+j)) //文字の照合

                                break;

                        else

                        {

                                i--;

                                j--;

                        }

                }

                if(j == -1)

                {

                        u = i+2;

                        break;

                }

                else

                {

                        i = i + n2 - j - 1;

                        i = i + ido_distance(p2,n2,*(p1+i));

                        j = n2 -1;

                }

        }

        cout << "照合回数：" << k << "回 \n";

        return (u);

}

int ido_distance(char* p2,int n2,char c)

{

        int n=1;

        while(n2-n)

        {

                if(c == *(p2+n2-n-1))

                {

                        cout << "移動" << n << "文字分\n";

                        return(n); // 文字列Pattern の右から n 番目の文字と同じなら

                                                // 移動距離は n 文字分

                        break;

                }

                else

                        n++;

        }

        cout << "移動" << n2 << "文字分。\n";

        return(n2);

}

int main(void)

{

        char Text[N1];

        char Pattern[N2];

        int k;  // 発見された位置

        int n1; // Text に入力された文字の個数

        int n2; // Pattern に入力された文字の個数

        // Text の読みこみ

        cout << "----Text の入力----\n";

        n1 = mojiretu_no_yomikomi(Text,N1);

        cout << "Text の入力は終了しました。\n"

                << "Text の文字数は" << n1 << "個です。\n";

        // Pattern の読みこみ

        cout << "----Pattern の入力----\n";

        n2 = mojiretu_no_yomikomi(Pattern,N2);

        cout << "Pattern の入力は終了しました。\n"

                << "Pattern の文字数は" << n2 << "個です。\n";

        // 方法１ による検索

        cout << "----方法１で検索中----\n";

        k = mojiretu_no_kennsaku_1(Text,Pattern,n1,n2);

        cout << "----検索終了----\n";

        // 方法１の結果の表示

        if (k <= n1-n2+1)

                cout << k << "文字めに見つかりました。\n";

        else

                cout << "見つかりませんでした。\n";

        // 方法２ による検索

        cout << "----方法２で検索中----\n";

        k = mojiretu_no_kennsaku_2(Text,Pattern,n1,n2);

        cout << "----検索終了----\n";

        // 方法２の結果の表示

        if (k <= n1-n2+1)

                cout << k << "文字めに見つかりました。\n";

        else

                cout << "見つかりませんでした。\n";

        return (0);

}