Cod sursa(job #1784214)

Utilizator GinguIonutGinguIonut GinguIonut Data 19 octombrie 2016 21:02:42
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <string.h>

#define nMax 2000001
#define solMax 1001

using namespace std;

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

int lenA, lenB, nrSol;
int pi[nMax], Sol[solMax];
char A[nMax], B[nMax];

void make_prefix(char A[], int lenA)
{
    int q=0;

    for(int i=2; i<=lenA; i++)
    {
        while(q>0 && A[q+1]!=A[i])
            q=pi[q];
        if(A[q+1]==A[i])
            q++;

        pi[i]=q;
    }
}

int str_match(char A[], int lenA, char B[], int lenB)
{
    int q=0;

    for(int i=1; i<=lenB; i++)
    {
        while(q>0 && A[q+1]!=B[i])
            q=pi[q];
        if(A[q+1]==B[i])
            q++;

        if(q==lenA)
        {
            nrSol++;
            if(nrSol<solMax-1)
                Sol[nrSol]=i-lenA;

            q=pi[q];
        }
    }
}

void read()
{
    fin>>(A+1), lenA=strlen(A+1);
    fin>>(B+1), lenB=strlen(B+1);
}

void write()
{
    fout<<nrSol<<'\n';
    for(int i=1; i<=min(solMax, nrSol); i++)
        fout<<Sol[i]<<" ";
}

void solve()
{
    make_prefix(A, lenA);
    str_match(A, lenA, B, lenB);
}

int main()
{
    read();
    solve();
    write();
}