Pagini recente » Cod sursa (job #504824) | Cod sursa (job #1721229) | Cod sursa (job #1951209) | Cod sursa (job #1363837) | Cod sursa (job #854470)
Cod sursa(job #854470)
#include<fstream>
#include<string>
#include<vector>
#define mod1 666001
#define mod2 666013
using namespace std;
string A,B;
vector <int> I;
int cod1,cod2,h1,h2,k2;
int litere(char c)
{
int x=0;
if (c>='A' && c<='Z') x=c-'A';
else if (c>='a' && c<='z') x=c-'a'+26;
else x=c-'0' +52;
return x;
}
void solveA()
{
int c1=0,c2=0;
int length=A.size();
for (int i=0;i<length;i++)
{
c1=((c1*62)%mod1+litere(A[i]))%mod1;
c2=((c2*62)%mod2+litere(A[i]))%mod2;
}
cod1=c1;
cod2=c2;
}
void solveB()
{
int k1,pow1=1,pow2=1;
int length=A.size();
for (int i=0;i<length;i++)
{
h1=((h1*62)%mod1+litere(B[i]))%mod1;
h2=((h2*62)%mod2+litere(B[i]))%mod2;
if (i>0)
{
pow1=(pow1*62)%mod1;
pow2=(pow2*62)%mod2;
}
}
k1=0;
if (h1==cod1 && h2==cod2)
{
k2++;
I.push_back(0);
}
int length2=B.size();
for (int i=length;i<length2;i++)
{
h1=(h1-(pow1*litere(B[k1]))%mod1+mod1)%mod1;
h2=(h2-(pow2*litere(B[k1]))%mod2+mod2)%mod2;
h1=((h1*62)%mod1+litere(B[i]))%mod1;
h2=((h2*62)%mod2+litere(B[i]))%mod2;
k1++;
if (h1==cod1 && h2==cod2)
{
k2++;
if (k2<=1000)
I.push_back(k1);
}
}
}
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
in>>A;
in>>B;
solveA();
solveB();
out<<k2<<"\n";
for (int i=0;i<I.size();i++)
{
out<<I[i]<<" ";
}
return 0;
}