Pagini recente » Cod sursa (job #3147469) | Cod sursa (job #382430) | Cod sursa (job #3147442) | Cod sursa (job #3293528) | Cod sursa (job #812693)
Cod sursa(job #812693)
#include<fstream>
#include<string>
#include<vector>
#define mod1 666001
#define mod2 1000007
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a,b;
vector <int> poz;
int cod1,cod2,h1,h2,nr;
void scan()
{
in>>a;
in>>b;
}
void code(int &cod1,int &cod2)
{
int l;
int k1=0,k2=0;
l=a.size()-1;
for (int i=0;i<=l;i++)
{
k1=((k1*26)%mod1+a[i]-'A')%mod1;
k2=((k2*26)%mod2+a[i]-'A')%mod2;
}
cod1=k1;
cod2=k2;
}
int putere1(int a,int b)
{
int k;
if (b==1)
return a;
if (b%2==0)
{
k=putere1(a,b/2);
return (k*k)%mod1;
}
return (a*putere1(a,b-1))%mod1;
}
int putere2(int a,int b)
{
int k;
if (b==1)
return a;
if (b%2==0)
{
k=putere2(a,b/2);
return (k*k)%mod2;
}
return (a*putere2(a,b-1))%mod2;
}
void solve()
{
int l;
int c,cc1,cc2;
l=a.size()-1;
for (int i=0;i<=l;i++)
{
h1=((h1*26)%mod1+b[i]-'A')%mod1;
h2=((h2*26)%mod2+b[i]-'A')%mod2;
}
c=0;
if (h1==cod1 && h2==cod2)
{
nr++;
poz.push_back(0);
}
for (int i=l+1;i<b.size();i++)
{
h1=h1-(putere1(26,l)*(b[c]-'A'))%mod1;
h2=h2-(putere2(26,l)*(b[c]-'A'))%mod2;
h1=((h1*26)%mod1+b[i]-'A')%mod1;
h2=((h2*26)%mod2+b[i]-'A')%mod2;
c++;
if (h1==cod1 && h2==cod2)
{
nr++;
poz.push_back(c);
}
}
}
void print()
{
out<<nr<<"\n";
for (int i=0;i<poz.size();i++)
out<<poz[i]<<" ";
}
int main()
{
scan();
code(cod1,cod2);
solve();
print();
return 0;
}