Cod sursa(job #856871)

Utilizator alinaelenaFMI Colceag Alina alinaelena Data 17 ianuarie 2013 00:49:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <cstdio>
#include <cstring>
 using namespace std;
#define nmax 2000001
#define baza 141
#define mod1 100007
#define mod2 100021
  
char a[nmax], b[nmax];
int m, n;
int h1, h2, pmax1, pmax2;
int gasit[nmax], k;
  
int main()
{
    int i;
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
      
    scanf("%s%s",&a,&b);
    n=strlen(a);
    m=strlen(b);
     
    if (n>m) { printf("0\n"); return 0;}
         
  
    pmax1=pmax2=1;
    h1=h2=0;
     
    for (i=0;i<n;++i)
    {
        h1=(h1*baza+a[i])%mod1;
        h2=(h2*baza+a[i])%mod2;
       if (i>0)
       { pmax1=(pmax1*baza)%mod1;
        pmax2=(pmax2*baza)%mod2;}
    }
  
  
    int hb1=0,hb2=0;
    for (i=0;i<n;++i)
       { hb1=(hb1*baza+b[i])%mod1;
        hb2=(hb2*baza+b[i])%mod2;}
  
    int nrgasit=0;
    if (h1==hb1&&h2==hb2)
        gasit[++k] = 0;
             
  
    for (i=n;i<m;++i)
    {
        hb1=((hb1-(b[i-n]*pmax1)%mod1+mod1)*baza+b[i])%mod1;
        hb2=((hb2-(b[i-n]*pmax2)%mod2+mod2)*baza+b[i])%mod2;
        
        if (h1==hb1&&h2==hb2)
        gasit[++k] = i-n+1;
         
    }
  
    printf("%d\n", k);
	for (i=1; i<=k && i<=1000; ++i)
		printf("%d ", gasit[i]);
	return 0;
}