Cod sursa(job #1261079)

Utilizator andreismara97Smarandoiu Andrei andreismara97 Data 11 noiembrie 2014 22:07:49
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include<cstdio>
#include<cstring>
using namespace std;

#define MAXN 2000003

char x[MAXN], y[MAXN];
int Pi[MAXN],d[MAXN];
int i,k,N,M;

void constructie_pi()  // construim pi-ul
{
    N=strlen(x)-1;
    Pi[1]=0;
    k=0;
    for(i=2;i<=N;i++)
    {
        while(k>0 && x[i]!=x[k+1])  // cat timp prefixul nu este nul si literele nu coincid
            k=Pi[k];                // sar din k la Pi[k]
        if(x[i]==x[k+1])
            k++;
        Pi[i]=k;
    }
}

int main ()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    fgets(x+1, MAXN, stdin);
    fgets(y+1, MAXN, stdin);

    x[0] = ' '; y[0] = ' ';
    x[strlen(x)-1] = y[strlen(y)-1] = 0;

    M=strlen(y)-1;
    constructie_pi(); //construim pi-ul
    k=0;
    for(i=1; i<=M; i++)
    {
        while(k>0 && y[i]!=x[k+1])
            k=Pi[k];
        if(y[i]==x[k+1])
            k++;
        d[i]=k;
    }
    int NR = 0;
    for(int i=1;i<= M;++i)
        if(d[i] == N)
            NR++;
    printf("%d\n",NR);
    for(int i=1;i<= M;++i)
        if(d[i] == N)
            printf("%d ",i-N);
    return 0;
}