Cod sursa(job #1860783)

Utilizator GinguIonutGinguIonut GinguIonut Data 28 ianuarie 2017 13:02:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 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, k, nrSol;

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

int main()
{
    fin>>A+1>>B+1;
    lenA=strlen(A+1), lenB=strlen(B+1);

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

    for(int i=1; i<=lenB; i++)
    {
        while(B[i]!=A[k+1] && k)
            k=pi[k];
        if(B[i]==A[k+1])
            k++;
        if(k==lenA)
        {
            nrSol++;
            if(nrSol<=1000)
                Sol[nrSol]=i-lenA;
            k=pi[k];
        }
    }

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