Pagini recente » Cod sursa (job #638670) | Cod sursa (job #954047) | Cod sursa (job #134795) | Cod sursa (job #2009431)
#include <fstream>
#include <string>
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
unsigned long long sph[20001000];
int pos[1005];
int main() {
string gasit;
string cautare;
cin>>gasit;
cin>>cautare;
int cont = 0;
int gsize = gasit.size();
int csize = cautare.size();
unsigned long long b='z' + 1;
unsigned long long hgasit = 0;
unsigned long long hash = 0;
for (int i=gsize; i>=0; i--){
hgasit *= b;
hgasit += gasit[i];
}
for (int i=csize; i>=0; i--){
sph[i] = sph[i+1]*b + cautare[i];
}
unsigned long long putgsize = 1;
for (int i=1; i<=gsize; i++){
putgsize = putgsize * b;
}
for (int i=0; i<=csize; i++){
hash = sph[i] - sph[i+gsize]*putgsize;
if (hash == hgasit){
cont++;
if (cont <= 1000){
pos[cont] = i;
}
}
}
cout<<cont<<'\n';
for (int i=1; i<= min(cont , 1000); i++){
cout<<pos[i]<<" ";
}
return 0;
}