Pagini recente » Cod sursa (job #3148662) | Cod sursa (job #1264084) | Cod sursa (job #2705895) | Cod sursa (job #194697) | Cod sursa (job #2122640)
#include <iostream>
#include <fstream>
#include <string.h>
#define MOD 666013
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n1,n2,val1,val2,put1,lg,sol[2000005];
const int baza=83;
char a[2000005],b[2000005];
bool ver(int x)
{
int i,lung;
lung=n1;
for(i=x;i>=x-n1+1;i--)
{
if(b[i]!=a[lung])
return 0;
lung--;
}
return 1;
}
int main()
{
fin>>(a+1)>>(b+1);
int i,putere=1;
n1=strlen(a+1);
n2=strlen(b+1);
lg=1;
for(i=n1;i>=1;i--)
{
if(i==1)
put1=putere;
val1+=((a[i]-64)*putere)%MOD; ///(int)
val1%=MOD;
putere*=baza;
putere%=MOD;
}
putere=1;
for(i=n1;i>=1;i--)
{
val2+=((b[i]-64)*putere)%MOD;
val2%=MOD;
putere*=baza;
putere%=MOD;
}
if(val1==val2)
{
if(ver(n1)==1)
{
sol[lg]=0;
lg++;
}
}
for(i=n1+1;i<=n2;i++)
{
val2=val2-((b[i-n1]-64)*put1)%MOD;
if(val2<0)
val2+=MOD;
val2=val2*baza;
val2+=b[i]-64;
val2%=MOD;
if(val1==val2)
{
if(ver(i)==1)
{
sol[lg]=i-n1;
lg++;
}
}
}
lg--;
fout << lg << '\n';
if(lg>1000)
lg=1000;
for(i=1;i<=lg;i++)
fout << sol[i] << ' ';
fout << '\n';
return 0;
}