Pagini recente » Cod sursa (job #2828700) | Cod sursa (job #2456616) | Cod sursa (job #108656) | Cod sursa (job #2142470) | Cod sursa (job #812700)
Cod sursa(job #812700)
#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*26+B[i]-'A')%MOD1,
Val2 = (Val2*26+B[i]-'A')%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*26+A[i]-'A')%MOD1,
aVal2 = (aVal2*26+A[i]-'A')%MOD2,
//printf("%d -> %d %d\n",i,aVal1,aVal2),
i ? (put1 = (put1*26)%MOD1,
put2 = (put2*26)%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]-'A')*put1)%MOD1;
aVal1 = (aVal1*26+A[i]-'A')%MOD1;
aVal2 = (aVal2+MOD2-(A[i-len]-'A')*put2)%MOD2;
aVal2 = (aVal2*26+A[i]-'A')%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]);
}