Cod sursa(job #1661714)

Utilizator vancea.catalincatalin vancea.catalin Data 24 martie 2016 09:01:06
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include<iostream>
#include<fstream>
#include<cstring>
#define DX 2000009
using namespace std;
fstream fin("strmatch.in",ios::in),fout("strmatch.out",ios::out);
char x[DX],y[DX];
int lx,ly,pr[DX],r[1010];
void sf()
{
    int i,j,poz=0;
    for(i=2;i<=lx;i++)
    {
        while(poz && x[poz+1]!=x[i])
        {
            poz=pr[poz];
        }
        if(x[poz+1]==x[i])
            poz++;
        pr[i]=poz;
    }
}
int main()
{
    int i,poz=0,lr=0;
    fin>>x>>y;
    lx=strlen(x);
    ly=strlen(y);
    for(i=lx;i>0;i--) x[i]=x[i-1];
    for(i=ly;i>0;i--) y[i]=y[i-1];
    sf();
    for(i=1;i<=ly;i++)
    {
        while(poz && x[poz+1]!=y[i])
        {
            poz=pr[poz];
        }
        if(x[poz+1]==y[i])
            poz++;
        if(poz==lx)
        {
            r[++lr]=i-lx;
        }
    }
    fout<<lr<<"\n";
    for(i=1;i<=lr;i++)
    {
        fout<<r[i]<<" ";
    }
}