Cod sursa(job #2163105)

Utilizator MentaPopa Marius-Catalin Menta Data 12 martie 2018 16:45:13
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 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,j;
    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";

    if ( N > 1000)
        for(int i = 0; i < 1000 ; i++)
            g<<sol[i]<< " ";
        else
            for(int i = 0; i < N ; i++)
            g<<sol[i]<< " ";

}