Cod sursa(job #1648645)

Utilizator LipanmateiLipan Radu-Matei Lipanmatei Data 11 martie 2016 11:07:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define Nmax 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char x[Nmax],y[Nmax];
int pi[Nmax];
int nrrez, rez[1001];

int main()
{
    // citire
    fin>>x+1>>y+1;
    x[0]=y[0]=' ';
    int n=strlen(x);
    int m=strlen(y);
    int k=0,i;
    pi[1]=0;
    // parcurgem x
    for(i=2;i<=n;i++)
    {
        // cautam pozitia optima in prefix unde putem adauga noul element
        while(k&&x[k+1]!=x[i])k=pi[k];
        // daca gasim pozitia marim k (adaugam noul element la vechiul prefix)
        if(x[k+1]==x[i])k++;
        // actualizam pozitia in care se termina prefixul care este si sufix pentru sirul x[i]
        pi[i]=k;
    }
    k=0;
    // parcurgem y
    for(i=1;i<=m;i++)
    {
        // cautam pozitia optima in prefix unde putem adauga noul element
        while(k&&x[k+1]!=y[i])k=pi[k];
        // daca gasim pozitia marim k (adaugam noul element la vechiul prefix)
        if(x[k+1]==y[i])k++;
        // daca lungimea prefixului coincide cu cea a sirului x atunci am gasit o potrivire
        if(k==n-1)
        {
            // marim numarul de rezultate
            nrrez++;
            if(nrrez<=1000)
                // adaugam noua pozitie
                rez[nrrez]=i-n+1;
        }
    }

    fout<<nrrez<<'\n';
    for(i=1;i<=min(nrrez,1000);i++)
        fout<<rez[i]<<' ';
    return 0;
}