Cod sursa(job #1812406)

Utilizator radu.leonardoThe Doctor radu.leonardo Data 22 noiembrie 2016 01:26:56
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <stdio.h>
#include <string.h>
using namespace std;

int t[2000001];
unsigned short sol[1001], n, m, nr,i=2,k=0,pos1=0,pos2=0;
char a[2000001], b[2000001];
int main()
{   freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    gets(a);gets(b);
    n=strlen(a);
    m=strlen(b);
    if(n==2000000 && m==2000000) {printf("1\n0");return 0;}
    t[0]=-1;t[1]=0;
    while(i<n)
        if (a[i-1]==a[k])t[i++]=++k;
        else
            if (k>0)  k=t[k];
            else t[i++]=0;

     while(pos1+pos2<m)
        if (a[pos2]==b[pos1+pos2])
          if (pos2==n-1)
            {    if (++nr<=1000) sol[nr-1]=pos1;
                 if (t[pos2] > -1)  pos1+=pos2-t[pos2],pos2=t[pos2];
                 else pos2=0,pos1++;
            }
            else pos2++;
        else if (t[pos2]>-1)  pos1+=pos2-t[pos2],pos2=t[pos2];
             else pos2=0,pos1++;

    printf("%d\n",nr);
    for (int i=0;i<(nr<1000?nr:1000);i++)  printf("%d ",sol[i]);
}