Cod sursa(job #1716750)

Utilizator antanaAntonia Boca antana Data 13 iunie 2016 17:57:37
Problema Potrivirea sirurilor Scor 36
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <cstdio>
#include<string.h>
#define MAX 2000000
#define R 1000
using namespace std;
char a[MAX+2], b[MAX+2];
int pi[MAX+2], n, m, rasp[MAX+2], r;
int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    int k=0;
    gets(a+1);
    gets(b+1);
    n=strlen(a+1);
    m=strlen(b+1);
    pi[1]=0;
    for(int i=2;i<=n;++i)
    {
        while((k>0) && (a[k+1]!=a[i]))
              k=pi[k];
        if(a[k+1]==a[i]);
            k++;
        pi[i]=k;
    }
    k=0;
    for(int i=1;i<=m;++i)
    {
        while((k>0) && (a[k+1]!=b[i]))
            k=pi[k];
        if(a[k+1]==b[i])
            k++;
        if(k==n && r<R)
            rasp[++r]=i-k+1;
    }
    printf("%d\n", r);
    for(int i=1;i<=r && i<=R;++i)
        printf("%d ", rasp[i]-1);
    return 0;
}