Cod sursa(job #298947)

Utilizator bacerandreiBacer Andrei bacerandrei Data 6 aprilie 2009 15:01:22
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include<stdio.h>
#include<string.h>
#define max 2000000
char a[max] , b[max];
long n , m , i , pi[max] , count , sol[max];


int main()
{
  freopen("strmatch.in" , "r" , stdin);
  freopen("strmatch.out" , "w" , stdout);
    scanf("%s" , &a);
    scanf("%s" , &b);
  n = strlen(a);
  m = strlen(b);

 int k = 0;
  pi[1] = 0;
   for(i = 2 ; i <= n ; i++)
    {
      while((k > 0) && (a[k] != a[i-1]))
	  k = pi[k];
	    if (a[k] == a[i-1])
	       k++;
	    pi[i] = k;
    }
    int q = 0;
      for(i = 1 ; i <= m ; i++)
       {
	 while((q > 0) && (a[q] != b[i-1]))
	  q = pi[q];
	if(a[q] == b[i-1])
	  q++;
       if(q == n)
	{
	 //printf("%d\n" , i-n);
	 count++;
	 sol[count] = i-n;
	}
      }
   printf("%d\n" , count);
    for(i = 1 ; i <= count ; i++)
     printf("%d " , sol[i]);
   return 0;
}