Cod sursa(job #1497286)

Utilizator Master011Dragos Martac Master011 Data 6 octombrie 2015 16:55:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include<cstdio>
using namespace std;

const int nMax = 4000010;
char s[nMax];
int Z[nMax], l, sl, af[nMax];

int strlg(char x[]){
    int i = 0;
    while(x[i] != 0) ++i;

    return i;
}

void fZ(){
    int L, R, k;
    L = R = 0;
    for(int i = 0 ; i < l ; ++i){
        if(i > R){
            L = R = i;
            while(s[R] == s[R - L]) ++R;
            Z[i] = R - L; --R;
        }else{
            k = i - L;
            if(Z[k] < R - i + 1){
                Z[i] = Z[k];
            }else{
                L = i;
                while(s[R] == s[R - L]) ++R;
                Z[i] = R - L; --R;
            }
        }
    }
}

int main (){
    FILE *in = fopen("strmatch.in","r");
    fgets(s, nMax, in);
    l = strlg(s);
    sl = l;
    s[l] = '!';
    fgets(s + l + 1, nMax, in);
    l = strlg(s);
    fclose(in);

    fZ();

    int sol = 0;
    for(int i = 0 ; i < l ; ++i){
        if(Z[i] >= sl - 1) af[++sol] = i;
    }

    FILE *out = fopen("strmatch.out","w");
    fprintf(out,"%d\n", sol);
    for(int i = 1 ; i <= sol && i <= 1000; ++i)
        fprintf(out,"%d ", af[i] - sl - 1);
    fprintf(out,"\n");
    fclose(out);
    return 0;
}