Cod sursa(job #1819160)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 30 noiembrie 2016 12:19:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.84 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>

#define BUF_SIZE 1<<17
char buf[BUF_SIZE];
int pbuf=BUF_SIZE;
FILE*fi,*fo;
inline char nextch(){
    if(pbuf==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fi);
        pbuf=0;
    }
    return buf[pbuf++];
}
inline long long nextnum(){
    long long a=0;
    char c=nextch();
    while((c<'0' || c>'9') && c!='-')
        c=nextch();
    int semn=1;
    if(c=='-'){
        semn=-1;
        c=nextch();
    }
    while('0'<=c && c<='9'){
        a=a*10+c-'0';
        c=nextch();
    }
    return a*semn;
}

#define MAXN 2000000
int n, m;
char N[1+2*MAXN];
int Z[1+2*MAXN];
int st[1+MAXN], last=0;

int main(){
    fi=fopen("strmatch.in","r");
    fo=fopen("strmatch.out","w");
    char c=nextch();
    while(c!='\n'){
        N[++n]=c;
        c=nextch();
    }
    m=n;
    c=nextch();
    while(c!='\n'){
        N[++n]=c;
        c=nextch();
    }

    int L=1, R=1;
    for(int k=2;k<=n;k++){
        if(k>R){
            int i=1, j=k;
            while(j<=n && N[i]==N[j]){i++;j++;}
            i--;j--;
            L=k;R=j;
            Z[k]=R-L+1;
        }
        else{
            int k2=k-L+1;
            if(Z[k2]<R-k+1)
                Z[k]=Z[k2];
            else{
                //printf("Da ");
                int i=R-k+2, j=R+1;
                //printf("%d %d\n", i, j);
                while(j<=n && N[i]==N[j]){i++;j++;}
                i--;j--;

                L=k;R=j;
                Z[k]=j-k+1;
            }
        }
        //printf("%d\n", Z[k]);
        if(k>m && Z[k]>=m)
            st[++last]=k-m-1;
    }
    fprintf(fo,"%d\n", last);
    if(last>1000)
        last=1000;
    for(int i=1;i<=last;i++)
        fprintf(fo,"%d ", st[i]);
    fclose(fi);
    fclose(fo);
    return 0;
}