Cod sursa(job #1043763)

Utilizator hevelebalazshevele balazs hevelebalazs Data 28 noiembrie 2013 22:13:14
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <stdio.h>
#include <string.h>
#define fr(i,a,b) for(int i=a;i<b;++i)
#define N 2000000
#define P 1000
char s[N+1],w[N+1];
int t[N],p[P];
int main(){
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%[^\n]s",w);
    scanf("\n");
    scanf("%[^\n]s",s);
    int pos=2,cnd=0;
    int wl=strlen(w),sl=strlen(s);
    t[0]=-1,t[1]=0;
    while(pos<wl){
        if(w[pos-1]==w[cnd]) t[pos]=++cnd,++pos;
        else if(cnd) cnd=t[cnd];
        else t[pos]=0,++pos;
        }

    int m=0,i=0;
    int pl=-1;

    while(m+i<sl){
        if(w[i]==s[m+i]){
            if(i==wl-1) {
                if(pl<P-1)p[++pl]=m;
                if(wl==1) ++i;
                else m+=i-t[i],i=t[i];
                }
            else ++i;
            }
        else{
            m+=i-t[i];
            i=(t[i]>-1)?t[i]:0;
            }
        }
    printf("%i\n",++pl);
    fr(i,0,pl)printf("%i ",p[i]);
    return 0;
    }