Pagini recente » Cod sursa (job #1754913) | Cod sursa (job #2242313) | Cod sursa (job #2226975) | Cod sursa (job #1790762) | Cod sursa (job #1914947)
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define lim 2000010
#define base 73
#define mod1 100007
#define mod2 100021
char a[lim], b[lim];
int rez[lim],n,m,numar1,numar2;
int main()
{
fin>>a;
fin>>b;
n=strlen(a);
m=strlen(b);
numar1=0, numar2=0;
for(int i=0; i<n; i++)
{
numar1 = (numar1*base+a[i]) % mod1;
numar2 = (numar2*base+a[i]) % mod2;
}
int nr1=0, nr2=0;
if(n>m)
{
fout<<0;
return 0;
}
int A1=1,B1=1;
for(int i=0; i<n; i++)
{
nr1 = (nr1*base+b[i]) % mod1;
nr2 = (nr2*base+b[i]) % mod2;
if(i)
{
A1=(A1*base)%mod1;
B1=(B1*base)%mod2;
}
}
int dr=0;
if(numar1==nr1 && numar2==nr2)
rez[++dr]=0;
for(int i=n; i<m; i++)
{
nr1 = ( ( nr1-(b[i-n]*A1)%mod1 + mod1 ) * base + b[i] ) % mod1;
nr2 = ( ( nr2-(b[i-n]*B1)%mod2 + mod2 ) * base + b[i] ) % mod2;
if(nr1==numar1 && nr2==numar2)
{
if(dr<1000)
rez[++dr]=i-n+1;
else dr++;
}
}
fout<<dr<<'\n';
int g=min(dr,1000);
for(int i=1; i<=g; i++)
fout<<rez[i]<<' ';
fin.close();
fout.close();
return 0;
}