Pagini recente » Cod sursa (job #1665529) | Cod sursa (job #353548) | Cod sursa (job #2011518) | Cod sursa (job #2960212) | Cod sursa (job #1183147)
#include <fstream>
#include <string>
#include <vector>
#include <list>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define PRIME 100007
// #define PRIME2 100021 - even more efficiency
#define D 123
string P, T;
int HashP, HashT, h = 1;
vector<int> s; int nos;
int main(){
int i, lgP, shift; char x;
fin >> P; lgP = P.size();
for (i = 0; i < lgP; i++)
HashP = (D * HashP + P[i]) % PRIME;
fin.get(x);
for (i = 0; i < lgP; i++){
fin.get(x); T += x;
HashT = (D * HashT + T[i]) % PRIME;
}
for (i = 1; i < lgP; i++) h = (h * D) % PRIME;
shift = 0;
while (!fin.eof()){
if (HashP == HashT){
for (i = 0; i < lgP; i++) if (P[i] != T[i + shift]) break;
if (i == lgP){
nos++;
if (nos < 1000)
s.push_back(shift);
}
}
fin.get(x); T += x;
HashT = ((HashT - (T[shift] * h) % PRIME + PRIME)*D + x) % PRIME;
shift++;
}
fout << nos << '\n';
for (i = 0; i < s.size() && i < 1000; i++) fout << s[i] << ' ';
return 0;
}