Cod sursa(job #2163145)

Utilizator MentaPopa Marius-Catalin Menta Data 12 martie 2018 16:53:40
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>


using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

const int nmax =  2000001;

char txt[nmax];
char pat[nmax];

vector <int> lps;
vector <int> sol;

int M,N;

void citire()
{
    f>>pat;
    M = strlen(pat);

    f>>txt;
    N = strlen(txt);
}

void setup()
{
    int i, len;

    i = 1;
    len = 0;
    lps.push_back(0);


    while ( i < M )
    {
        if( pat[i] == pat [len] )
        {
            lps.push_back(++len);
            ++i;
        }

        else {
                if( len != 0 )
                len = lps[len-1];

                else
                {
                    lps.push_back(0);
                    ++i;
                }
        }

    }
}


void solve ()
{
    int i=0,j=0;
    while( i < N )
    {
        if ( txt[i] == pat[j] )
        {
            ++i;
            ++j;
        }

        if ( j == M)
        {
            sol.push_back(i-j);
            j = lps[j-1];
        }

        if ( txt[i] != pat[j] && i < N )
        {
            if ( j != 0)
                j = lps[j-1];
            else
                ++i;
        }
    }
}


int main()
{
    citire();
    setup();
    solve();
    int N = sol.size();
    g << N << "\n";

    for ( int i = 0; i < min(N,1000) ; i++ )
        g<<sol[i]<< " " ;

}