Pagini recente » Cod sursa (job #999968) | Borderou de evaluare (job #491036) | Cod sursa (job #813814) | Cod sursa (job #1818490) | Cod sursa (job #373583)
Cod sursa(job #373583)
#include<fstream>
#include<string>
#include<vector>
#include<stdlib.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
class strmatchRK
{
public:
string A,B;
int LenA,LenB,Pow,E;
int a,b,q;
vector <int> S;
strmatchRK(const int baza)
{
E=baza;
a=b=0;
q=171110003;
}
void Read()
{
f>>A;
f>>B;
LenA=A.size();
LenB=B.size();
if(LenA>LenB)
{
g<<"0\n";
exit(0);
}
}
void Print()
{
g<<S.size()<<'\n';
for(int i=0;i<(int)S.size();i++)
g<<S[i]<<' ';
g<<'\n';
}
void PreCalc()
{
for(int i=0;i<LenA;i++)
{
a=(a*E+A[i])%q;
b=(b*E+B[i])%q;
}
}
int Putere(int a,int b)
{
int rez=1;
a%=q;
while(b)
{
if(b%2)
rez=rez*a%q;
a=a*a%q;
b>>=1;
}
return rez;
}
bool cmp(int s)
{
for(int i=s,j=0;i<s+LenA;i++,j++)
if(A[j]!=B[i])
return 0;
return 1;
}
void RK()
{
Pow=Putere(E,LenA-1);
for(int i=0;i+LenA<=LenB+1;i++)
{
if(S.size()>1000)
break;
if(a==b)
{
if(cmp(i))
S.push_back(i);
}
if(i<=LenB-LenA)
b=(E*(b-B[i]*Pow)%q+B[i+LenA])%q;
}
}
};
int main()
{
strmatchRK RK(73);
RK.Read();
RK.PreCalc();
RK.RK();
RK.Print();
return 0;
}