Cod sursa(job #1425334)

Utilizator costyv87Vlad Costin costyv87 Data 27 aprilie 2015 12:20:17
Problema Potrivirea sirurilor Scor 26
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <cstdio>
#include <string.h>
#include <vector>
using namespace std;

#define nmax 4000100

FILE *f,*g;
char a[nmax],b[nmax/2];
int Z[nmax];
int P;
int sol[1010],cn;


void Z_algorithm()
{
    int L,R,i,j,k,n = strlen(a),ind,d;
    L = R = 0;

    for (i=2;i<n;i++)
    {
        if (i>R)
        {
            if (a[1] == a[i])
            {
                L = i;
                for (j=1,k=i,R=i-1;k<n && a[j] == a[k];j++,k++) Z[i]++,R++;

            }
            else
                Z[i] = 0;
        }
        else
        {
            ind = i-L+1;
            if (Z[ind]<R-i+1)
            {
                Z[i] = Z[ind];
            }
            else
            {
                Z[i] = R-i+1;

                d =Z[i]+1;
                for(;R+1<n && a[R+1] == a[d];R++,d++) Z[i]++;
            }
        }

        if (i>P && Z[i]>=P)
        {
            if (cn<1000)
                sol[++cn] = i-P-1;
            else
                cn++;
        }
    }
}

int main()
{
    f=fopen("strmatch.in","r");
    g=fopen("strmatch.out","w");

    a[0] = '~';
    fscanf(f,"%s",a+1);
    P = strlen(a)-1;

    fscanf(f,"%s",b);
    strcat(a,b);

    Z_algorithm();
    fprintf(g,"%d\n",cn);
    if (cn<1000)
        for (int i=1;i<=cn;i++)
            fprintf(g,"%d ",sol[i]);
    else
        for (int i=1;i<=1000;i++)
            fprintf(g,"%d ",sol[i]);

    return 0;
}