#include <iostream>
#include <string>
#include <conio.h>
#include <cstdlib>

using namespace std;

void wczytanie(string &tekst, string &wzor);
void naiwny(string tekst, string wzor, int &dlt, int &dlw);
void zbudujKmp(string wzor, int dlw, int p[]);
void KMP(string wzor, string tekst, int dlw, int dlt, int p[]);

void wczytanie(string &tekst, string &wzor)
{
    cout << "Podaj tekst: ";
    getline(cin, tekst);
    cout<<"Dlugosc tekstu ze spacjami to: "<< tekst.length() <<endl;

    cout << "Podaj wzorzec: ";
    getline(cin, wzor);
    cout<<"Dlugosc wzorca ze spacjami to: "<< wzor.length() <<endl;

}

void naiwny(string tekst, string wzor, int &dlt, int &dlw)
{
    dlt=tekst.length();
    dlw=wzor.length();
    int i=0;
    while (i<=dlt-dlw)
    {
        int j=0;
        while (j<dlw && wzor[j]==tekst[i+j])
        {
            j++;
        }

        if(j==dlw)
        {
            cout<<i<<endl;
        }

        i++;
    }

}

void zbudujKmp(string wzor, int dlw, int p[])
{
    p[0]=0;
    p[1]=0;
    int t=0;
    int i=1;
    while (i<dlw)
    {
        while (t>0 && wzor[t]!=wzor[i])
        {
            t=p[t];
        }

        if (wzor[t]==wzor[i])
        {
            t++;
        }

        p[i+1]=t;
        i++;
    }
    }

void KMP(string wzor, string tekst, int dlw, int dlt, int p[])
{
    int i=0;
    int j=0;

    while (i<(dlt-dlw+1))
    {
        while(wzor[j]==tekst[i+j]&&j<dlw)
        {
            j++;
        }

        if (j==dlw)
        {
            cout<<i<<endl;
        }

        i=i+max(1,j-p[j]);
        j=p[j];
    }
}

int main()
{
    string tekst, wzor;
    int dlt, dlw;

    int wybor;
    cout<<"Menu:"<<endl;
    cout<<"1.Wczytanie\n2.Algorytm naiwny\n3.Algorytm KMP"<<endl;

    cout<<"Twoj wybor: ";
    wybor=getch();
    cout<<char(wybor)<<endl;

    switch (wybor)
    {
    case '1':
        {
            wczytanie(tekst, wzor);
            break;
        }
    case '2':
        {
            wczytanie(tekst, wzor);
            cout<<"ALGORYTM NAIWNY"<<endl;
            cout<<"Indeksy elementow w ktorych zaczyna sie wzorzec:"<<endl;
            naiwny(tekst, wzor, dlt, dlw);
            break;
        }
    case '3':
        {
            wczytanie(tekst, wzor);
            cout<<"ALGORYTM KMP"<<endl;
            cout<<"Indeksy elementow w ktorych zaczyna sie wzorzec:"<<endl;
            dlw = wzor.length();
            int p[dlw];
            zbudujKmp(wzor, dlw, p);
            KMP(wzor, tekst, dlw, dlt, p);

            break;
        }
    default:
        {
            cout<<"NIEPOPRAWNY WYBOR!!!";
            break;
        }
    }





}