Cod sursa(job #2276055)

Utilizator Vlad_lsc2008Lungu Vlad Vlad_lsc2008 Data 4 noiembrie 2018 00:19:47
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb

#include<iostream>

#include<fstream>

#include<cstring>

#include<queue>

using namespace std;

char a[4000010],b[2000010];

int z[4000010];

queue<int> sol;



int main()

{

    int n=0;

    int i,k,len1,len;

    ifstream t1("strmatch.in");

    ofstream t2("strmatch.out");

    t1.get(a,2000010); t1.get();

    len1=strlen(a);

    t1.get(b,2000010);

    strcat(a,"@");

    strcat(a,b);

    len=strlen(a);



    int L=0,R=0;

    for(i=1;i<len;i++)

    {

        if( i>R)

        {

            L=R=i;

            while( R<len && a[R-L]==a[R])

                R++;

            z[i]=R-L;

            R--;

        }

        else

        {

            k=i-L;

            if( z[k]< R-i+1 )

                z[i]=z[k];

            else

            {

                L=i;

                while( R<len && a[R-L]==a[R])

                    R++;

                z[i]=R-L;

                R--;

            }

        }

        if(z[i]==len1)

        {

            n++;

            sol.push(i-len1-1);

        }

    }



    t2<<n<<'\n';

    for(i=1;i<=min(1000,n);i++,sol.pop())

        t2<<sol.front()<<' ';

    t2<<'\n';

    return 0;



}