Cod sursa(job #1755649)

Utilizator giotoPopescu Ioan gioto Data 10 septembrie 2016 18:35:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <cstdio>
#include <cstring>
#define NMAX 2000005
using namespace std;

int n,m,pi[NMAX],pos[1024];
char a[NMAX],b[NMAX];
int minim(int x,int y){
    return (x<y)?x:y;
}
void make_prefix(){
    int q=0;
    for(int i=2;i<=m;++i){
        pi[1]=0;
        while(q&&a[q+1]!=a[i])
            q=pi[q];
        if(a[q+1]==a[i])
            ++q;
        pi[i]=q;
    }

}
int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    fgets(a,sizeof(a),stdin);
    fgets(b,sizeof(b),stdin);
    n=strlen(b),m=strlen(a);--m;--n;
    for(int i=m;i;--i)a[i]=a[i-1]; a[0]=' ';
    for(int i=n;i;--i)b[i]=b[i-1]; b[0]=' ';
    make_prefix();
    int q=0,nr=0;
    for(int i=1;i<=n;++i){
        while(q&&a[q+1]!=b[i])
            q=pi[q];
        if(a[q+1]==b[i])
            ++q;
        if(q==m){
            q=pi[m];++nr;
            if(nr<=1000)
                pos[nr]=i-m;
        }
    }printf("%d\n", nr);
    for(int i=1;i<=minim(nr,1000);++i)
        printf("%d ",pos[i]);

    return 0;
}