Cod sursa(job #1656815)

Utilizator feli2felicia iuga feli2 Data 19 martie 2016 20:27:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <iostream>
#include <fstream>
#include <string.h>

using namespace std;

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

const int Nmax=2000005;

int na, P[Nmax], nb, nr, Rez[1005];
char A[Nmax], B[Nmax];

void pref()
{
    int p=0;
    for(int i=2;i<=na;i++)
    {
        while(p&&A[p+1]!=A[i])
            p=P[p];
        if(A[p+1]==A[i])
            p++;
        P[i]=p;
    }
}

int main()
{
    char c;
    na=nb=0;
    c=fin.get();
    while(c!='\n')
    {
        na++;
        A[na]=c;
        c=fin.get();
    }
    c=fin.get();
    while(c!='\n')
    {
        nb++;
        B[nb]=c;
        c=fin.get();
    }
    pref();
    int p=0;
    for(int i=1;i<=nb;i++)
    {
        while(p&&A[p+1]!=B[i])
            p=P[p];
        if(A[p+1]==B[i])
            p++;
        if(p==na)
        {
            nr++;
            if(nr<=1000)
                Rez[nr]=i-na;
        }
    }
    fout<<nr<<'\n';
    for(int i=1;i<=min(nr,1000);i++)
        fout<<Rez[i]<<" ";
    fout<<'\n';
    return 0;
}