Cod sursa(job #1656769)

Utilizator feli2felicia iuga feli2 Data 19 martie 2016 19:27:59
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 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[1000];
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<1000)
        {
            nr++;
            Rez[nr]=i-na;
        }
    }
    fout<<nr<<'\n';
    for(int i=1;i<=nr;i++)
        fout<<Rez[i]<<" ";
    fout<<'\n';
    return 0;
}