cakod 2/1

#include<iostream>
#include<string>
#include<vector>
#include <string>
#include <string.h>
#include <time.h>
#include <ctime>

#define d 256

using namespace std;

vector<int> prefix_function(const string& s) {//Boyer-Moore Algoritması
    vector<int> pi(s.length(), 0);

    clock_t start = 0, end = 0;

    start = clock();
    for (size_t i = 0; i < 1000; i++) {

        for (int i = 1; i < s.length(); i++) {//pi onu hersayının kendini tekrar edisi
                                              //eger iki sayi varsa o zaman pi artmaya baslar
                                              //000120 gibi tekrar sayılarına bakar en bastan baslar
            int j = pi[i - 1];

            while (j > 0 && s[i] != s[j]) {
                j = pi[j - 1];
            }

            if (s[i] == s[j]) {
                pi[i] = j + 1;
            }
            else {
                pi[i] = j;
            }
        }
    }

    end = clock();
    cout << endl << "time = " << ("The above code block was executed in %.4f second(s)\n", ((double)end - start) / ((double)CLOCKS_PER_SEC)) << endl;
    return pi;
}

//*******************************************************************************************
void search(char pat[], char txt[], int q)//Rabin-Karp String
{
    int M = strlen(pat);
    int N = strlen(txt);
    int i, j;
    int p = 0; //karma deger pat
    int t = 0; // karma deger txt
    int h = 1;

    ///bu bulmak için "pow(d, M-1)%q"
    for (i = 0; i < M - 1; i++)
        h = (h * d) % q;

    //ilk yazı değerini hesaplama
    for (i = 0; i < M; i++)
    {
        p = (d * p + pat[i]) % q;
        t = (d * t + txt[i]) % q;
    }
    //deseni metinde tek tek kaydırmak için kullanılan denklem
    clock_t start = 0, end = 0;

    start = clock();
    for (int r = 0; r < 1000000; r++) {
        if (r == 999999 ) {
            for (i = 0; i <= N - M; i++)
            {


                if (p == t)
                {

                    for (j = 0; j < M; j++)
                    {
                        if (txt[i + j] != pat[j])
                            break;
                    }

                    //eger p == t and pat[0...M-1] = txt[i, i+1, ...i+M-1]
                    if (j == M)
                        cout << "sirasi: " << i << endl;
                }

                //önde gelen rakamı sonrayı ekleme
                if (i < N - M)
                {
                    t = (d * (t - txt[i] * h) + txt[i + M]) % q;


                    if (t < 0)
                        t = (t + q);
                }
            }
        }
    }
    end = clock();
    cout << endl << "time = " << ("The above code block was executed in %.4f second(s)\n", ((double)end - start) / ((double)CLOCKS_PER_SEC)) << endl;
}
/**********************************************************************************************/
int KMPSearch(char* string, char* substring) { //Knuth–Morris–Pratt Algorithm
    int  sl, ssl;
    int res = -1;
    sl = strlen(string);
    ssl = strlen(substring);

    clock_t start = 0, end = 0;

    start = clock();
    for (size_t r = 0; r < 10000; r++) {
        if (sl == 0)                                                    //satir dogrulama
            cout << "Неверно задана строка\n";
        else if (ssl == 0)                                            //dogrulama
            cout << "Неверно задана подстрока\n";
        else {
            int  i, j = 0, k = -1;
            int* w;
            w = new int[1000];                                         //yeni massiv yaratma
            w[0] = -1;
            while (j < ssl - 1) {
                while (k >= 0 && substring[j] != substring[k]) /*kadar k daha büyük veya eşit 0 ve J
                    - thy eleman alt dize eşit değil k - Tom atamak k - thy eleman dinamik bir dizi */
                    k = w[k];
                j++;
                k++;
                if (substring[j] == substring[k])
                    w[j] = w[k];
                else
                    w[j] = k;
            }
            i = 0;
            j = 0;                                                        //sıfırlandı
            while (j < ssl && i < sl) {
                while (j >= 0 && string[i] != substring[j])
                    j = w[j];
                i++;
                j++;
            }


            delete[] w;
            res = j == ssl ? i - ssl : -1;         //sonuç, j = ssl ve -1 ise i-ssl olacaktır
        }
    }

    end = clock();
    cout << endl << "time = " << ("The above code block was executed in %.4f second(s)\n", ((double)end - start) / ((double)CLOCKS_PER_SEC)) << endl;

    return res;
}

int main() {
    string s, t;
    cin >> s >> t;

    vector<int> pi = prefix_function(t + '#' + s);

    int t_len = t.length();

    for (int i = 0; i < s.length(); i++) {
        if (pi[t_len + 1 + i] == t_len) {
            cout << "s[" << i - t_len + 1 << ".." << i << "] = t" << endl;
        }
    }

    cout << "********************************************************************************************" << endl;
    char txt[] = "qwertyxvbalpayqwefnvfx";
    char pat[] = "alpay";

    //prime sayısı
    int q = 101;

    search(pat, txt, q);

    cout << "********************************************************************************************" << endl;

    char alp[] = "qwertyxvbalpayqwefnvfx";
    char mal[] = "alpay";
    cout << KMPSearch(alp, mal);


    return 0;

}