Cod sursa(job #855435)

Utilizator alinaelenaFMI Colceag Alina alinaelena Data 14 ianuarie 2013 22:53:19
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <cstdio>
#include <string.h>
#include<vector>
 using namespace std;
#define nmax 2000001
#define baza 61
#define mod1 100007
#define mod2 100021
 
char a[nmax], b[nmax];
int m, n;
int h1, h2, pmax1, pmax2;
vector <int> gasit;
 
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.push_back(0); nrgasit++;}
			
 
    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.push_back(i-n+1); nrgasit++;}
        
    }
    printf("%d\n", nrgasit);
 
  
    for (int i = 0; i <gasit.size()%1000; i++)
          printf("%d ",gasit[i]);
    printf("\n");
     
    return 0;
}