Pagini recente » Cod sursa (job #2167326) | Cod sursa (job #1361129) | Cod sursa (job #1086951) | Cod sursa (job #2499738) | Cod sursa (job #1183207)
#include <fstream>
#include <string>
#include <vector>
#include <list>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define PRIME1 100007
#define PRIME2 100021
#define D 123
string P, T;
int hashP1, hashT1, h1 = 1;
int hashP2, hashT2, h2 = 1;
vector<int> s; int nos;
int main(){
int i, lgP, lgT, shift; char x;
fin >> P; lgP = P.size();
for (i = 0; i < lgP; i++)
hashP1 = (D * hashP1 + P[i]) % PRIME1,
hashP2 = (D * hashP2 + P[i]) % PRIME2;
fin.get(x); fin >> T; lgT = T.size();
/*if (lgP > lgT) { fout << "0 \n"; return 0; }
if (P == T) { fout << "1\n" << "0 \n"; return 0; }*/
for (i = 0; i < lgP; i++){
hashT1 = (D * hashT1 + T[i]) % PRIME1,
hashT2 = (D * hashT2 + T[i]) % PRIME2;
}
for (i = 1; i < lgP; i++)
h1 = (h1 * D) % PRIME1,
h2 = (h2 * D) % PRIME2;
shift = 0;
while (shift <= lgT - lgP){
if (hashP1 == hashT1 && hashP2 == hashT2){
for (i = 0; i < lgP; i++) if (P[i] != T[i + shift]) break;
if (i == lgP){
nos++;
if (nos <= 1000)
s.push_back(shift);
}
}
hashT1 = ((hashT1 - (T[shift] * h1) % PRIME1 + PRIME1)*D + x) % PRIME1;
hashT2 = ((hashT2 - (T[shift] * h2) % PRIME2 + PRIME2)*D + x) % PRIME2;
shift++;
}
fout << nos << '\n';
for (i = 0; i < s.size() && i < 1000; i++) fout << s[i] << ' ';
return 0;
}