Cod sursa(job #1813738)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 23 noiembrie 2016 11:23:45
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>

#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 pi[1+MAXN];
int N[1+MAXN], M[1+MAXN];
int n, m;
inline int getPi(){
    pi[1]=0;
    int k=0;
    for(int i=2;i<=n;i++){
        while(k>0 && N[k+1]!=N[i])
            k=pi[k];
        if(N[k+1]==N[i])
            k++;
        pi[i]=k;
    }
}

int st[1+MAXN], ind=0;

int main(){
    fi=fopen("strmatch.in","r");
    fo=fopen("strmatch.out","w");
    char c=nextch();
    while(c!='\n' && c!=EOF){
        N[++n]=c;
        c=nextch();
    }
    c=nextch();
    while(c!='\n' && c!=EOF){
        M[++m]=c;
        c=nextch();
    }
    getPi();
    int q=0;
    for(int i=1;i<=m;i++){
        while(q>0 && N[q+1]!=M[i])
            q=pi[q];
        if(N[q+1]==M[i])
            q++;
        if(q==n)
            st[ind++]=i;
    }
    fprintf(fo,"%d\n", ind);
    for(int i=0;i<ind;i++)
        fprintf(fo,"%d ", st[i]-n);
    fclose(fi);
    fclose(fo);
    return 0;
}