Pagini recente » Cod sursa (job #1420937) | Cod sursa (job #3252095) | Cod sursa (job #2694176) | Cod sursa (job #889342) | Cod sursa (job #2466755)
#include <fstream>
#include <cmath>
#include <cstring>
#define MOD1 666013
#define MOD2 1000000007
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int l1, l2, r[3],rm[3], rc[3], sol, v[2000100],P;
char sir1[2000100], sir2[2000100];
int ind(char ch);
int main()
{
cin>>sir1;
cin.get();
cin>>sir2;
l1=strlen(sir1);
l2=strlen(sir2);
rm[1]=rm[2]=1;
for(int i=0; i<l1; ++i)
{
rc[1]=(rc[1]*10+ind(sir1[i]))%MOD1;
rc[2]=(rc[2]*10+ind(sir1[i]))%MOD2;
if(i){
rm[1]=(rm[1]*10)%MOD1;
rm[2]=(rm[2]*10)%MOD2;
}
}
for(int i=0; i<l1; ++i)
{
r[1]=(r[1]*10+ind(sir2[i]))%MOD1;
r[2]=(r[2]*10+ind(sir2[i]))%MOD2;
}
if(r[1]==rc[1] && r[2]==rc[2])
v[++sol]=0;
P=pow(10,l1-1);
for(int i=l1; i<l2; ++i)
{
r[1]=(r[1]+(MOD1-rm[1]*ind(sir2[i-l1]))%MOD1)%MOD1;
r[1]=r[1] *10 +ind(sir2[i]); r[1]%=MOD1;
r[2]=(r[2]+(MOD2-rm[2]*ind(sir2[i-l1]))%MOD2)%MOD2;
r[2]=r[2] *10 +ind(sir2[i]); r[2]%=MOD2;
if(r[1]==rc[1] && r[2]==rc[2])
v[++sol]=i-l1+1;
}
cout<<sol<<'\n';
for(int i=1; i<=sol; ++i)
cout<<v[i]<<' ';
cout<<'\n';
return 0;
}
int ind(char ch)
{
if(ch>='a' && ch<='z')
return 27+ch-'a';
else return ch-'A'+1;
}