Cod sursa(job #1830829)

Utilizator Vlad1111Sbengheci Vlad-Andrei Vlad1111 Data 17 decembrie 2016 10:38:45
Problema Potrivirea sirurilor Scor 8
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
#include <cstdio>
#include <string.h>
#define cout cerr
#define MAX 2000005

using namespace std;

char a[MAX],b[MAX],n,m;
int suf[MAX],i,j;
int nrn, loc[MAX];

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    scanf("%s %s",a+1,b+1);
    a[0]=b[0]='-';
    n=strlen(a)-1;
    m=strlen(b)-1;

    j=0;
    suf[1]=0;
    for(i=2; i<=n; i++)
    {
        if(a[i]==a[j+1])
            suf[i]=++j;
        else
        {
            while(a[i]!=a[j] && j!=0)
                j=suf[j-1];
            suf[i]=j;
        }
    }

    j=1;

    for(int i=1; i<=m && nrn<1000; i++)
    {
        if(b[i]==a[j+1] && j<=n)
            j++;
        else
        {
            j--;
            while(b[i]!=a[j] && j!=0)
            {
                j=suf[j];
            }
        }
        if(j>=n)
            loc[nrn++]=i;
    }

    printf("%d\n",nrn);
    for(i=0;i<nrn;i++)
        printf("%d ",loc[i]-n);
    return 0;
}