Cod sursa(job #1199858)

Utilizator livliviLivia Magureanu livlivi Data 20 iunie 2014 21:48:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include<cstdio>
using namespace std;

char a[2000001],b[2000001];
int pred[2000001];
int rez[2000001];

int main(){
    freopen ("strmatch.in","r",stdin);
    freopen ("strmatch.out","w",stdout);
    int n,m,i,k,cnt;

    scanf ("%s\n",a+1);
    scanf ("%s",b+1);
    n=0;
    while(b[n+1]!='\0') n++;
    m=0;
    while(a[m+1]!='\0') m++;

    pred[1]=0;
    k=0;
    for(i=2;i<=m;i++){
        while(k>0 &&a[k+1]!=a[i]) k=pred[k];
        if (a[k+1]==a[i]) k++;
        pred[i]=k;
    }

    k=0;
    cnt=0;
    for(i=1;i<=n;i++){
        while(cnt>0 &&a[cnt+1]!=b[i]) cnt=pred[cnt];
        if (a[cnt+1]==b[i]) cnt++;
        if (cnt==m){
            k++;
            rez[k]=i-m;
            cnt=pred[cnt];
        }
    }

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

    return 0;
}