Pagini recente » Cod sursa (job #552840) | Cod sursa (job #1942945) | Monitorul de evaluare | Profil M@2Te4i | Cod sursa (job #2470751)
#include <fstream>
#include <cmath>
#include <cstring>
#define MOD1 1000000007
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
long long l1, l2, r,rm, rc, v[2000100],P;
int sol;
char sir1[2000100], sir2[2000100];
int ind(char ch);
void scan();
void print();
int main()
{
scan();
rm=1; rc=0;
for(int i=0; i<l1; ++i)
{
rc=(rc*10+ind(sir1[i]))%MOD1;
if(i)
rm=(rm*10)%MOD1;
}
r=0;
for(int i=0; i<l1; ++i)
r=(r*10+ind(sir2[i]))%MOD1;
if(r==rc)
v[++sol]=0;
for(int i=l1; i<l2; ++i)
{
r=(r+(MOD1-rm*ind(sir2[i-l1]))%MOD1)%MOD1;
r=r *10 +ind(sir2[i]); r%=MOD1;
if(r==rc)
v[++sol]=i-l1+1;
}
print();
return 0;
}
void scan()
{
cin>>sir1;
cin.get();
cin>>sir2;
l1=strlen(sir1);
l2=strlen(sir2);
}
int ind(char ch)
{
if(ch>='a' && ch<='z')
return 27+ch-'a';
else return ch-'A'+1;
}
void print()
{
cout<<sol<<'\n';
for(int i=1; i<=min(sol,1000); ++i)
cout<<v[i]<<' ';
cout<<'\n';
}