Pagini recente » Cod sursa (job #2203224) | Cod sursa (job #3323527) | Cod sursa (job #2209775) | Cod sursa (job #2209774) | Cod sursa (job #2209770)
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char smodel[2000001],s[2000001];
const int MOD1=666013,MOD2=1000000009,B=67;
int v[2000001];
int main()
{
long long r1=0,r2=0,rmodel1=0,rmodel2=0,n1,n2,i,put1=1,put2=1,cnt=0;
in>>(smodel+1);
in>>(s+1);
n1=strlen(smodel+1);
n2=strlen(s+1);
for(i=1; i<=n1; i++)
{
if(i>=2)
{
put1=put1*B%MOD1;
put2=put2*B%MOD2;
}
rmodel1=rmodel1*B;
if(smodel[i]>='A'&&smodel[i]<='Z')
rmodel1+=smodel[i]-'A'+27;
else if(smodel[i]>='a'&&smodel[i]<='z')
rmodel1+=smodel[i]-'a'+1;
else
rmodel1+=smodel[i]-'0'+53;
rmodel1%=MOD1;
rmodel2=rmodel2*B;
if(smodel[i]>='A'&&smodel[i]<='Z')
rmodel2+=smodel[i]-'A'+27;
else if(smodel[i]>='a'&&smodel[i]<='z')
rmodel2+=smodel[i]-'a'+1;
else
rmodel2+=smodel[i]-'0'+53;
rmodel2%=MOD2;
}
for(i=1; i<=n2; i++)
{
r1=(long long)r1*B;
if(s[i]>='A'&&s[i]<='Z')
r1+=s[i]-'A'+27;
else if(s[i]>='a'&&s[i]<='z')
r1+=s[i]-'a'+1;
else
r1+=s[i]-'0'+53;
r1%=MOD1;
r2=(long long)r2*B;
if(s[i]>='A'&&s[i]<='Z')
r2+=s[i]-'A'+27;
else if(s[i]>='a'&&s[i]<='z')
r2+=s[i]-'a'+1;
else
r2+=s[i]-'0'+53;
r2%=MOD2;
if(i>=n1)
{
if(rmodel1==r1&&rmodel2==r2)
v[++cnt]=i-n1;
if(s[i-n1+1]>='A'&&s[i-n1+1]<='Z')
r1=r1+MOD1-(long long)put1*(s[i-n1+1]-'A'+27)%MOD1;
else if(s[i-n1+1]>='a'&&s[i-n1+1]<='z')
r1=r1+MOD1-(long long)put1*(s[i-n1+1]-'a'+1)%MOD1;
else
r1=r1+MOD1-(long long)put1*(s[i-n1+1]-'0'+53)%MOD1;
r1%=MOD1;
if(s[i-n1+1]>='A'&&s[i-n1+1]<='Z')
r2=r2+MOD2-(long long)put2*(s[i-n1+1]-'A'+27)%MOD2;
else if(s[i-n1+1]>='a'&&s[i-n1+1]<='z')
r2=r2+MOD2-(long long)put2*(s[i-n1+1]-'a'+1)%MOD2;
else
r2=r2+MOD2-(long long)put2*(s[i-n1+1]-'0'+53)%MOD2;
r2%=MOD2;
}
}
out<<cnt<<'\n';
for(i=1;i<=cnt;i++)
out<<v[i]<<" ";
return 0;
}