Cod sursa(job #1591048)

Utilizator dodecagondode cagon dodecagon Data 5 februarie 2016 18:52:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 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)
    {
      if (nr < 1000) pp[nr++]=i-k-1; else nr++;
    }
printf("%u\n",nr);
if (nr > 1000) nr=1000;
for (ul i=0;i<nr;i++)
     printf("%u ",pp[i]);
    return 0;
}