Cod sursa(job #151156)

Utilizator AlxCojocaru Alexandru Alx Data 7 martie 2008 21:00:04
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <stdio.h>
#include <string.h>
//using namespace std;
char a[2000003],b[2000003];
int pi[2000003];
int main()
{
 freopen("strmatch.in","r",stdin);
 freopen("strmatch.out","w",stdout);
 scanf("%s\n%s\n",&a,&b);
 long m=strlen(a),n=strlen(b),i,q=0,nr=0,pos[1000];
 for (i=m;i>0;i--)
  a[i]=a[i-1];
 a[0]=' ';
 for (i=n;i>0;i--)
  b[i]=b[i-1];
 b[0]=' ';
 pi[1]=0;
 for (i=2;i<=m;i++)
 {
  while (q&&a[q+1]!=a[i])
   q=pi[q];
  if (a[q+1]==a[i])
   q++;
  pi[i]=q;
 }
 q=0;
 for (i=1;i<=n;i++)
 {
  while (q&&a[q+1]!=b[i])
   q=pi[q];
  if (a[q+1]==b[i])
   q++;
  if (q==m)
   if (nr<1000)
   {
    pos[nr]=i-m;
    nr++;
    q=pi[q];
   }
 }
 printf("%ld\n",nr);
 for (i=0;i<nr;i++)
  printf("%ld ",pos[i]);
 return 0;
}