Cod sursa(job #1249914)

Utilizator deea101Andreea deea101 Data 27 octombrie 2014 17:26:08
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <cstring>
#define SMAX 2000001
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

char A[SMAX], B[SMAX];
int fail[SMAX];
int N, countSol, sol[10000];

void prefix()
{
    fail[1]=0;
    int nod=0;

    int i;

    for(i=2;i<=strlen(A+1);i++)
    {
        while(nod!=0 && A[i]!=A[nod]+1)
            nod=fail[nod];

        if(A[i]==A[nod+1])
            nod++;

        fail[i]=nod;
    }
}

int main()
{
    f.getline(A+1,SMAX);
    f.getline(B+1,SMAX);

    prefix();

    int i,nod=0;
    for(i=1;i<=strlen(B+1);i++)
    {
        while(nod!=0 && B[i]!=A[nod+1])
            nod=fail[nod];

        if(B[i]==A[nod+1])
            nod++;

        if(nod==strlen(A+1))
        {
            if(countSol<1000) sol[++countSol]=i-strlen(A+1);
            nod=fail[nod];
        }
    }

    g<<countSol<<'\n';
    for(i=1;i<=countSol;i++) g<<sol[i]<<' ';
}