Pagini recente » Cod sursa (job #1937462) | Cod sursa (job #757183) | Cod sursa (job #502291) | Cod sursa (job #2283943) | Cod sursa (job #1282313)
//Deresu Roberto - FMI
//Re :)
#include<fstream>
#include<cstring>
#define mod1 12345
#define mod2 54321
#define p 26
#define nx 2000007
using namespace std;
int n,m,p1,p2,vala1,vala2,valb1,valb2,nrsol,sol[nx];
char a[nx],b[nx];
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int main()
{
fin>>a>>b;
m = strlen(a);
n = strlen(b);
p1 = p2 = 1;
for(int i=0;i<m;i++)
{
vala1 = (vala1*p+a[i])%mod1;
vala2 = (vala2*p+a[i])%mod2;
valb1 = (valb1*p+b[i])%mod1;
valb2 = (valb2*p+b[i])%mod2;
}
if(vala1 == valb1 && vala2 == valb2) sol[++nrsol] = 0;
for(int i=1;i<m;i++)
{
p1 = (p1*p)%mod1;
p2 = (p2*p)%mod2;
}
for(int i=m;i<n;i++)
{
valb1 = ((valb1 - (p1*b[i-m])%mod1+mod1)*p + b[i])%mod1;
valb2 = ((valb2 - (p2*b[i-m])%mod2+mod2)*p + b[i])%mod2;
if(vala1 == valb1 && vala2 == valb2) sol[++nrsol] = i;
}
fout<<nrsol<<'\n';
if(nrsol>1000)
nrsol = 1000;
for(int i=1;i<=nrsol;i++)
fout<<sol[i]<<" ";
return 0;
}