Cod sursa(job #1591034)

Utilizator dodecagondode cagon dodecagon Data 5 februarie 2016 18:41:31
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include<stdio.h>
#include<cstring>
#define nmax 4000001
#define ul unsigned long

char s[nmax];
ul z[nmax],n,nr,pp[1024];




int main()
{
   freopen("strmatch.in","r",stdin);
   freopen("strmatch.out","w",stdout);
char * p=s;
scanf("%s",p);
int k=strlen(p);
strcat(p,"$");
p=p+k+1;
scanf("%s",p);

ul n=strlen(s);
ul r=0,l=0;
for (ul i=1;i<n;i++)
{
   if (i>r)
   {
      r=l=i;
      while (r<n && s[r]==s[r-l])
          r++;
      z[i]=r---l;
   } else
   {
       if (z[i-l]< r-i+1)
         z[i]=z[i-l]; else
       {
          l=i;
           while (r<n && s[r]==s[r-l])
             r++;
           z[i]=r---l;
       }
   }
}
 for (ul i=k+1;i<n;i++)
    if (z[i]==k && nr<1000)
     pp[nr++]=i-k-1;
printf("%u\n",nr);
for (ul i=0;i<nr;i++)
     printf("%u ",pp[i]);
    return 0;
}