Cod sursa(job #162489)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 20 martie 2008 08:49:57
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <stdio.h>
#include <string.h>

int n, m, pi[2000005], poz[1024];
char a[2000005], b[2000005];

inline int minim(int x, int y) {return x < y ? x : y;}

void citire()
{
   freopen("strmatch.in","r",stdin);
   freopen("strmatch.out","w",stdout);

   fgets(a,2000005,stdin); n = strlen(a) - 1;
   fgets(b,2000005,stdin); m = strlen(b) - 1;

   int i;
   for (i = n; i >= 1; i--) a[i] = a[i - 1]; a[0] = ' ';
   for (i = m; i >= 1; i--) b[i] = b[i - 1]; b[0] = ' ';
}

void prefix()
{
   int i, q = 0;

   for (i = 2, pi[1] = 0; i <= n; i++)
   {
      while (q && a[q + 1] != a[i]) q = pi[q];
      if (a[q+1] == a[i]) q++;
      pi[i] = q;
   }
}

int main()
{
   int i, q = 0, nr;
   citire();
   prefix();

   for (i = 2; i <= m; i++)
   {
      while (q && a[q + 1] != b[i]) q = pi[q];
      if (a[q + 1] == b[i]) q++;
      if (q == n)
      {
	 q = pi[n];
	 nr++;
	 if (nr <= 1000)  poz[nr] = i - n;
      }
   }

   printf("%d\n",nr);
   for (i = 1; i <= minim(nr,1000); i++) printf("%d ",poz[i]);
   printf("\n");
   return 0;
}