Pagini recente » Cod sursa (job #181755) | Cod sursa (job #742056) | Cod sursa (job #908076) | Cod sursa (job #898964) | Cod sursa (job #629760)
Cod sursa(job #629760)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
const int B=67;
const int P=666013;
string S1,S2;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int Poz[2000000],nrpoz=0;
int nrAp=0;
void Read()
{
fin>>S1>>S2;
}
int putereB()
{
int aux=1;
for(int i=1;i<=S1.size()-1;i++)
aux=(aux*B)%P;
return aux;
}
void S1Baza()
{
int poz;
int Ha=S1[0],Hb=S2[0];
int sizeS1=S1.size(),sizeS2=S2.size();
int putere=putereB();
for(int i=1;i<sizeS1;i++)
{
Ha=((Ha*B)%P + S1[i])%P;
}
for(int i=1;i<sizeS1;i++)
{
Hb=((Hb*B)%P + S2[i])%P;
}
int flag=1,j,l;
if(Hb==Ha)
{
for(j=0;j<sizeS1;j++)
if(S1[j]!=S2[j])
{
flag=0;
break;
}
if (flag)
Poz[nrpoz++]=0;
nrAp++;
}
int k=0;
while (k != (sizeS2-sizeS1))
{
Hb = (P + Hb - (S2[k] * putere) % P) % P;
Hb = (Hb * B ) % P;
Hb = (Hb + S2[k + sizeS1 ]) % P;
k++;
if(Hb==Ha)
{
flag=1;
for(l=0,j=k;j<=k+sizeS1-1 && l<sizeS1;j++,l++)
if(S1[l]!=S2[j])
{
flag=0;
break;
}
if (flag)
Poz[nrpoz++]=k;
nrAp++;
}
}
}
int main()
{
Read();
S1Baza();
fout<<nrAp<<"\n";
for(int i=0;i<nrpoz;i++)
fout<<Poz[i]<<" ";
return 0;
}