Pagini recente » Borderou de evaluare (job #2898081) | Autentificare | Cod sursa (job #2656287) | Cod sursa (job #1454904) | Cod sursa (job #815300)
Cod sursa(job #815300)
#include<fstream>
#include<string>
#include<vector>
#define mod1 666001
#define mod2 666013
#define factor 62
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;
}
inline int caracter(char x)
{
int ch;
if (x>='A' && x<='Z')
ch=x-'A';
else
if (x>='a' && x<='z')
ch=x-'a'+26;
else ch=x-'0'+52;
return ch;
}
void code(int &cod1,int &cod2)
{
int l,ch;
int k1=0,k2=0;
l=a.size()-1;
for (int i=0;i<=l;i++)
{
ch=caracter(a[i]);
k1=((k1*factor)%mod1+ch)%mod1;
k2=((k2*factor)%mod2+ch)%mod2;
}
cod1=k1;
cod2=k2;
}
void solve()
{
int l,ch;
int c,cc1,cc2,putere1=1,putere2=1;
l=a.size()-1;
for (int i=0;i<=l;i++)
{
ch=caracter(b[i]);
h1=((h1*factor)%mod1+ch)%mod1;
h2=((h2*factor)%mod2+ch)%mod2;
if (i)
{
putere1=(putere1*factor)%mod1;
putere2=(putere2*factor)%mod2;
}
}
c=0;
if (h1==cod1 && h2==cod2)
{
nr++;
poz.push_back(0);
}
for (int i=l+1;i<b.size();i++)
{
ch=caracter(b[c]);
h1=(h1-(putere1*ch)%mod1+mod1)%mod1;
h2=(h2-(putere2*ch)%mod2+mod2)%mod2;
ch=caracter(b[i]);
h1=((h1*factor)%mod1+ch)%mod1;
h2=((h2*factor)%mod2+ch)%mod2;
c++;
if (h1==cod1 && h2==cod2)
{
nr++;
if (nr<=1000)
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;
}