Cod sursa(job #1216498)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 4 august 2014 18:32:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <cstring>
#define NMAX 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char Nb1[2*NMAX],Nb2[2*NMAX],Nb3[2*NMAX];
int Solution[1005];
long long Result;
int Z[2*NMAX];
int N,M,L,R;
void Read()
{
    f.getline(Nb2,NMAX);
    f.getline(Nb1,NMAX);
    N=strlen(Nb1);
    M=strlen(Nb2);
    for(int i=M;i<=M+N-1;i++)
        Nb2[i]=Nb1[i-M];
    for(int i=1;i<=M+N;i++)
        Nb3[i]=Nb2[i-1];
}

int newPosition(int k,int start)
{
    int result=0;
    while(Nb3[start]==Nb3[k] && k<=N+M)
    {
        result++;
        start++;
        k++;
    }
    return result;
}

void precalcZ()
{
    int i;
    Z[1]=M+N;
    for(int k=2;k<=M+N;k++)
    {
        if(k>R)
        {
            Z[k]=newPosition(k,1);
            L=k;R=k+Z[k]-1;
        }
        else
        {
            int aux=k-L+1;
            if(Z[aux]<R-k+1)
                Z[k]=Z[aux];
            else
            {
                int poz=R+1+newPosition(R+1,R-k+2);
                Z[k]=poz-k;R=poz-1;L=k;
            }
        }
    }
}

void Browse()
{
    int i;
    for(i=M+1;i<=N+1;i++)
        if(Z[i]>=M)
        {
            Result++;
            if(Solution[0]<1000)
                Solution[++Solution[0]]=i-M-1;
        }
    g<<Result<<"\n";
    for(int i=1;i<=Solution[0];i++)
        g<<Solution[i]<<" ";
}
int main()
{
    Read();
    precalcZ();
    Browse();
    return 0;
}