Pagini recente » Cod sursa (job #3004861) | Cod sursa (job #696642) | Cod sursa (job #49865) | Cod sursa (job #2980338) | Cod sursa (job #2976901)
#include <fstream>
#include<vector>
#include<cstring>
#define BAZA 73
#define MOD1 100007
#define MOD2 104729
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s[2000005],t[2000005];
int n,m,h1,h2,sol;
int v[2000005];
int main()
{
fin>>s;
fin>>t;
n=strlen(s);
m=strlen(t);
if(n>m)
{
fout<<0;
return 0;
}
int p1=1;
int p2=1;
int hs1=0;
int hs2=0;
for(int i=0;i<n;i++)
{
hs1=(hs1*BAZA+s[i])%MOD1;
hs2=(hs2*BAZA+s[i])%MOD2;
if(i!=0)
{
p1=(p1*BAZA)%MOD1;
p2=(p2*BAZA)%MOD2;
}
}
int ht1=0;
int ht2=0;
for(int i=0;i<n;i++)
{
ht1=(ht1*BAZA+t[i])%MOD1;
ht2=(ht2*BAZA+t[i])%MOD2;
}
if(hs1==ht1&&hs2==ht2)
{
v[0]=1;
sol++;
}
for(int i=n;i<m;i++)
{
ht1 = ((ht1 - (t[i - n] * p1) % MOD1 + MOD1) * BAZA + t[i]) % MOD1;
ht2 = ((ht2 - (t[i - n] * p2) % MOD2 + MOD2) * BAZA + t[i]) % MOD2;
if(hs1==ht1&&hs2==ht2)
{
v[i-n+1]=1;
sol++;
}
}
fout<<sol<<"\n";
int k=0;
for(int i=0;i<m &&k<1000;i++)
{
if(v[i])
{
fout<<i<<" ";
k++;
}
}
return 0;
}