Nu aveti permisiuni pentru a descarca fisierul grader_test37.ok
Cod sursa(job #1550156)
Utilizator | Data | 13 decembrie 2015 12:37:37 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 28 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.1 kb |
#include <cstdio>
#include <cstring>
#define p 73
#define m1 100007
#define m2 100021
using namespace std;
char A[2000001],B[2000001],C[2000001];
int n,a1,b1,a2,b2,nr,na,nb,i;
long long p1=1,p2=1;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s\n%s",&A,&B);
na=strlen(A);
nb=strlen(B);
if(na>nb)
{
printf("0\n");
return 0;
}
for(i=0; i<na; i++)
{
a1=(a1*p+A[i])%m1;
a2=(a2*p+A[i])%m2;
b1=(b1*p+B[i])%m1;
b2=(b2*p+B[i])%m2;
if(i!=0)
{
p1=(p1*p)%m1;
p2=(p2*p)%m2;
}
}
if(a1==b1 && a2==b2)
{
C[0]=1;
nr++;
}
for(i=na; i<nb; i++)
{
b1=((b1-(B[i-na]*p1)%m1+m1)*p+B[i])%m1;
b2=((b2-(B[i-na]*p2)%m2+m2)*p+B[i])%m2;
if(a1==b1 && a2==b2)
{
C[i-na+1]=1;
nr++;
}
}
printf("%d\n",nr);
nr=1;
for(i=0; i<nb && i<1000; i++)
if(C[i]==1)
printf("%d ",i);
return 0;
}