Cod sursa(job #1198653)

Utilizator livliviLivia Magureanu livlivi Data 16 iunie 2014 15:54:25
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include<string.h>
#include<cstdio>
using namespace std;

char a[2000002];
char b[2000002];
int pref[2000001];
int rasp[2000001];
int k;

int main(){
    freopen ("strmatch.in","r",stdin);
    freopen ("strmatch.out","w",stdout);
    int n=1,m=1,i,pot;
    scanf ("%s\n",&a);
    scanf ("%s",&b);
    n=strlen(a);
    m=strlen(b);
    for(i=n;i>0;i--) a[i]=a[i-1];
    for(i=m;i>0;i--) b[i]=b[i-1];

    //pref[i]= lungimea celui mai lung prefix al lui a, de lungime <i, care incepe in b[1], b[2] ... b[i]
    pref[1]=0;
    for(i=2;i<=n;i++){
        k=pref[i-1];
        while(k>0 &&a[k+1]!=a[i])
            k=pref[k];
        if (a[k+1]==a[i]) k++;
        pref[i]=k;
        //printf ("%d\n",pref[i]);
    }


    k=0;
    pot=0;
    for(i=1;i<=m;i++){
        //printf ("%d\n",pot);
        while(pot>0 &&a[pot+1]!=b[i])
            pot=pref[pot];
        //printf ("%d\n",pot);
        if (a[pot+1]==b[i])
            pot++;
        //printf ("%d\n",pot);
        if (pot==n){
            k++;
            rasp[k]=i-n;
        }
        //printf ("%d\n",pot);
    }

    printf ("%d\n",k);
    if (k>1000) k=1000;
    for(i=1;i<=k;i++)
        printf ("%d ",rasp[i]);
    return 0;
}