Pagini recente » Cod sursa (job #1800460) | Cod sursa (job #2058723) | Cod sursa (job #1413656) | Cod sursa (job #2109072) | Cod sursa (job #2974189)
#include <fstream>
#include <cstring>
#define MOD1 1000000007
#define MOD2 1000000009
#define b 62
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
char s1[2000010],s2[2000010];
int v[1010];
int transforma(char ch)
{
int val;
if ('a'<=ch && ch<='z')
val=ch-'a';
if ('A'<=ch && ch<='Z')
val=ch-'A'+26;
if ('0'<=ch && ch<='9')
val=ch-'0'+52;
return val;
}
int main()
{
long long n1,n2,nr1_mod1,nr1_mod2,nr2_mod1,nr2_mod2,b_putere_mod1,b_putere_mod2,i,ct=0,inc,sf;
cin>>s1>>s2;
n1=strlen(s1);
n2=strlen(s2);
b_putere_mod1=1;
b_putere_mod2=1;
nr1_mod1=transforma(s1[n1-1]);
nr1_mod2=transforma(s1[n1-1]);
nr2_mod1=transforma(s2[n1-1]);
nr2_mod2=transforma(s2[n1-1]);
for (i=n1-2; i>=0; i--)
{
b_putere_mod1=(b_putere_mod1*b)%MOD1;
b_putere_mod2=(b_putere_mod2*b)%MOD2;
nr1_mod1=(nr1_mod1+b_putere_mod1*transforma(s1[i])%MOD1)%MOD1;
nr1_mod2=(nr1_mod2+b_putere_mod2*transforma(s1[i])%MOD2)%MOD2;
nr2_mod1=(nr2_mod1+b_putere_mod1*transforma(s2[i])%MOD1)%MOD1;
nr2_mod2=(nr2_mod2+b_putere_mod2*transforma(s2[i])%MOD2)%MOD2;
}
if (nr1_mod1==nr2_mod1 && nr1_mod2==nr2_mod2)
{
ct++;
v[ct]=0;
}
for (i=n1; i<=n2-1; i++)
{
inc=i-n1+1;
sf=i;
nr2_mod1=(nr2_mod1-b_putere_mod1*transforma(s2[inc-1])%MOD1+MOD1)%MOD1;
nr2_mod1=nr2_mod1*b%MOD1;
nr2_mod1=(nr2_mod1+transforma(s2[sf]))%MOD1;
nr2_mod2=(nr2_mod2-b_putere_mod2*transforma(s2[inc-1])%MOD2+MOD2)%MOD2;
nr2_mod2=nr2_mod2*b%MOD2;
nr2_mod2=(nr2_mod2+transforma(s2[sf]))%MOD2;
if (nr1_mod1==nr2_mod1 && nr1_mod2==nr2_mod2)
{
ct++;
if (ct<=1000)
v[ct]=inc;
}
}
cout<<ct<<"\n";
if (ct<=1000)
for (i=1; i<=ct; i++)
cout<<v[i]<<" ";
else
for (i=1; i<=1000; i++)
cout<<v[i]<<" ";
return 0;
}