Pagini recente » Cod sursa (job #2584003) | Cod sursa (job #1624535) | Cod sursa (job #1562788) | Cod sursa (job #590630) | Cod sursa (job #2208617)
#include <fstream>
#include <cstring>
using namespace std;
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
const long long baza=62;
const long long p=961748941;
char a[2000003],b[2000003];
int poz[2000003];
long long put=1,rp=0,n,m,cnt=0;;
void citire ()
{
in.getline(a,2000000);
in>>ws;
in.getline(b,2000000);
m=strlen(a);
n=strlen(b);
for(int i=0;i<m;++i)
{
if(a[i]>='0' && a[i]<='9')
a[i]=a[i]-'0';
if(a[i]>='a' && a[i]<='z')
a[i]=a[i]-'a'+10;
if(a[i]>='A' && a[i]<='Z')
a[i]=a[i]-'A'+36;
}
for(int i=0;i<n;++i)
{
if(b[i]>='0' && b[i]<='9')
b[i]=b[i]-'0';
if(b[i]>='a' && b[i]<='z')
b[i]=b[i]-'a'+10;
if(b[i]>='A' && b[i]<='Z')
b[i]=b[i]-'A'+36;
}
}
void frmput ()
{
for(int i=0;i<m;++i)
put=(long long)(put*1LL*baza)%p;
}
void frmrp ()
{
for(int i=0;i<m;++i)
{
rp=(long long)(rp*1LL*baza)%p;
rp=(long long)(rp+a[i])%p;
}
}
void rez ()
{
long long i,rc=0;
for(i=0;i<n;++i)
{
rc=(long long)(rc*1LL*baza)%p;
rc=(long long)(rc+b[i])%p;
if(i>=m)
{
rc=(long long)(rc+p-(put*1LL*b[i-m])%p)%p;
if(rc==rp)
poz[++cnt]=i-m+1;
}
if(rc==rp && i==m-1)
poz[++cnt]=i-m+1;
}
}
int main()
{
citire();
frmput();
frmrp();
rez();
out<<cnt<<'\n';
if(cnt>=1000)
cnt=1000;
for(int i=1;i<=cnt;++i)
out<<poz[i]<<' ';
return 0;
}