Pagini recente » Cod sursa (job #1834185) | Cod sursa (job #1213293) | Cod sursa (job #664733) | Cod sursa (job #1286506) | Cod sursa (job #812713)
Cod sursa(job #812713)
#include<stdio.h>
FILE *f = fopen("strmatch.in","r");
FILE *g = fopen("strmatch.out","w");
#define MaxN 2000100
#define MOD1 666013
#define MOD2 1123001
#define MaxSol 1100
int Val1,Val2,Sol;
int SolV[MaxSol];
char A[MaxN],B[MaxN];
void citire(void)
{
fgets(B,sizeof(B),f);
fgets(A,sizeof(A),f);
}
void preprocesare(void)
{
for(int i=0;B[i] != '\n';i++)
Val1 = (Val1*256+B[i])%MOD1,
Val2 = (Val2*256+B[i])%MOD2;
}
void rezolvare(void)
{
int aVal1 = 0,aVal2 = 0,i,put1=1,put2=1,len;
preprocesare();
for(i=0;B[i] != '\n';i++)
aVal1 = (aVal1*256+A[i])%MOD1,
aVal2 = (aVal2*256+A[i])%MOD2,
//printf("%d -> %d %d\n",i,aVal1,aVal2),
i ? (put1 = (put1*256)%MOD1,
put2 = (put2*256)%MOD2) : 0;
len = i;
for(;A[i];i++)
{
if(aVal1 == Val1 && aVal2 == Val2)
if(++Sol <= 1000)
SolV[Sol] = i-len;
aVal1 = (aVal1+MOD1-(A[i-len]*put1)%MOD1)%MOD1;
aVal1 = (aVal1*256+A[i])%MOD1;
aVal2 = (aVal2+MOD2-(A[i-len]*put2)%MOD2)%MOD2;
aVal2 = (aVal2*256+A[i])%MOD2;
//printf("%d -> %d %d\n",i,aVal1,aVal2);
}
}
int main()
{
citire();
rezolvare();
fprintf(g,"%d\n",Sol);
for(int i=1;i<=1000 && i<=Sol;i++)
fprintf(g,"%d ",SolV[i]);
}