Cod sursa(job #1201937)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 26 iunie 2014 14:31:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include<cstdio>
const int N=2000000,MAX_OUTPUT=1000;
int prefix[N+1],res[N+1];
char s1[N+1],s2[N+1];
FILE*in,*out;
int n1,n2,noRes;
void scan(){
    fscanf(in,"%s\n",s2);
    fscanf(in,"%s",s1);
}
int stringLenght(char s[N+1]){
    int i=0;
    while(s[i]!='\0')
        i++;
    return i;
}
void shift(){
    int i;
    for(i=n1;i>=1;i--)
        s1[i]=s1[i-1];
    for(i=n2;i>=1;i--)
        s2[i]=s2[i-1];
}
void init(){
    in=fopen("strmatch.in","r");
    out=fopen("strmatch.out","w");
    scan();
    n1=stringLenght(s1);
    n2=stringLenght(s2);
    shift();
}
void setPrefix(){
    int i,k=0;
    prefix[1]=0;
    for(i=2;i<=n2;i++){
        while(k>0&&s2[i]!=s2[k+1])
            k=prefix[k];
        if(s2[i]==s2[k+1])
            k++;
        prefix[i]=k;
    }
}
int min2(int a,int b){
    if(a<b)
        return a;
    return b;
}
void print(){
    int i;
    fprintf(out,"%d\n",noRes);
    noRes=min2(noRes,MAX_OUTPUT);
    for(i=1;i<=noRes;i++)
        fprintf(out,"%d ",res[i]-1);
}
void solve(){
    int i,k=0;
    setPrefix();
    for(i=1;i<=n1;i++){
        while(k>0&&s1[i]!=s2[k+1])
            k=prefix[k];
        if(s1[i]==s2[k+1])
            k++;
        if(k==n2){
            res[++noRes]=i-n2+1;
            k=prefix[k];
        }
    }
    print();
}
void closeFiles(){
    fclose(in);
    fclose(out);
}
int main(){
    init();
    solve();
    closeFiles();
    return 0;
}