Pagini recente » Cod sursa (job #1911686) | Cod sursa (job #1328167) | Cod sursa (job #2467315) | Cod sursa (job #967499) | Cod sursa (job #373872)
Cod sursa(job #373872)
#include<fstream>
#include<string>
#include<vector>
#include<stdlib.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define ll long long
class strmatchRK
{
public:
string A,B;
int LenA,LenB,N,Pow,E;
int a[2],b[2],q[2],p[2];
vector <int> S;
strmatchRK(const int baza)
{
E=baza;
a[0]=a[1]=b[0]=b[1]=0;
q[0]=100007;q[1]=100021;
N=0;
}
void Read()
{
f>>A;
f>>B;
LenA=A.size();
LenB=B.size();
if(LenA>LenB)
{
g<<"0\n";
exit(0);
}
}
void Print()
{
g<<N<<'\n';
for(int i=0;i<(int)S.size();i++)
g<<S[i]<<' ';
g<<'\n';
}
int Putere(int a,int b,int q)
{
long rez=1;
a=a%q;
while(b)
{
if(b%2)
rez=(ll)rez*a%q;
a=(ll)a*a%q;
b/=2;
}
return rez;
}
void RK()
{
for(int i=0;i<LenA;i++)
{
a[0]=(a[0]*E+A[i])%q[0];
a[1]=(a[1]*E+A[i])%q[1];
b[0]=(b[0]*E+B[i])%q[0];
b[1]=(b[1]*E+B[i])%q[1];
}
p[0]=Putere(E,LenA-1,q[0]);
p[1]=Putere(E,LenA-1,q[1]);
for(int i=0;i+LenA-1<=LenB;i++)
{
if(a[0]==b[0]&&a[1]==b[1])
{
N++;
if(N<=1000)
S.push_back(i);
}
if(i+LenA<=LenB)
{
b[0]=((b[0]-(B[i]*p[0])%q[0]+q[0])*E+B[i+LenA])%q[0];
b[1]=((b[1]-(B[i]*p[1])%q[1]+q[1])*E+B[i+LenA])%q[1];
}
}
}
};
int main()
{
strmatchRK RK(123);
RK.Read();
RK.RK();
RK.Print();
return 0;
}