Pagini recente » Cod sursa (job #1381931) | Cod sursa (job #2415037) | Cod sursa (job #120825) | Cod sursa (job #451792) | Cod sursa (job #629768)
Cod sursa(job #629768)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int B=67;
const int P=666013;
string S1,S2;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int nrpoz=0;
int nrAp=0;
vector<int> Poz;
void Read()
{
fin>>S1>>S2;
}
int putereB()
{
int aux=1;
int s = S1.size();
for(int i=1; i<= s;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;
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.push_back(0);
}
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.push_back(k);
}
}
}
int main()
{
Read();
S1Baza();
int k = Poz.size();
fout<<k<<"\n";
int minim = min( 1000,k);
for(int i=0;i<minim;i++)
fout<<Poz[i]<<" ";
fout<<"\n";
return 0;
}