Cod sursa(job #151779)

Utilizator AlxCojocaru Alexandru Alx Data 8 martie 2008 16:47:20
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <stdio.h>
#include <string.h>
using namespace std;
char a[2000005],b[2000005];
int pi[2000005],pos[1024];
int main()
{
 freopen("strmatch.in","r",stdin);
 freopen("strmatch.out","w",stdout);
 scanf("%s\n%s\n",&a,&b);
 long n,m,i,q=0,nr=0;
 m=strlen(a);
 n=strlen(b);
 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)
  {
   q=pi[m];
   if (nr<1000)
   {
    pos[nr]=i-m;
    nr++;
   }
  }
 }
 printf("%ld\n",nr);
 for (i=0;i<nr;i++)
  printf("%d ",pos[i]);
 return 0;
}