Cod sursa(job #2714287)

Utilizator bostanlucastefanBostan Luca-Stefan bostanlucastefan Data 1 martie 2021 17:27:23
Problema Potrivirea sirurilor Scor 24
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
#include <cstring>
#define fq 2000002
#define num 1000

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

string A,B;
int nr,lg,i;
int p[fq],sol[fq];

int main()
{
    //input
    fin>>A>>B;

    //solution
    for(i=1; i<A.size(); i++)
    {
        while(lg && A[lg]!=A[i])
            lg-p[lg-1];
        if(A[lg]==A[i])
            lg++;
        p[i]=lg;
    }

    lg=0;

    for(i=0; i<B.size(); i++)
    {
        while(lg && A[lg]!=B[i])
            lg=p[lg-1];
        if(A[lg]==B[i])
            lg++;
        if(lg==A.size())
            sol[++nr]=i+1-A.size(), lg=p[lg-1];
    }

    //output
    fout<<nr<<'\n';
    for(i=1; i<=min(nr,num); i++)
        fout<<sol[i]<<' ';
    fout<<'\n';
    return 0;
}