Pagini recente » Cod sursa (job #2204272) | Cod sursa (job #323693) | Cod sursa (job #2879483) | Cod sursa (job #500719) | Cod sursa (job #913602)
Cod sursa(job #913602)
#include <fstream>
#include <cassert>
#include <vector>
#include <cstring>
//#include <iostream>
using namespace std;
static const int MOD = 666013, A = 62, MAXL = 2000009;
int v[1009];
char s1[MAXL], s2[MAXL];
inline int dig(char c) {
int ans = 0;
assert(('A' <= c && c <= 'Z') || ('a' <= c && c <= 'z') || ('0' <= c && c <= '9'));
if(c >= 'a') {
ans = (c - 'a') + 36;
}
else if(c >= 'A') {
ans = (c - 'A') + 10;
}
else {
ans = (c - '0');
}
return ans;
}
int main() {
int i, kt = 0;
ifstream f("strmatch.in");
f >> s2 >> s1;
f.close();
//cout << s2 << endl;
//cout << s1 << endl;
ofstream g("strmatch.out");
int n1 = strlen(s1);
int n2 = strlen(s2);
if(n1 < n2) {
g << "0\n";
}
else {
int j, hP(0), hT(0), Ap = 1;
for(i = 0; s2[i]; i++) {
hP = (hP * A + dig(s2[i])) % MOD;
//cout << dig(s2[i]) << endl;
}
//cout << hP << endl;
int l = n2 - 1;
for(i = 0; i < l; i++) {
hT = (hT * A + dig(s1[i])) % MOD;
//cout << hT << endl;
Ap = (Ap * A) % MOD;
}
for(i = l; s1[i]; i++) {
hT = ((hT * A) + dig(s1[i])) % MOD;
//cout << hT << endl;
if(hT == hP) {//possible match
for(j = 0; s2[j]; j++) {
if(s2[j] != s1[i - l + j]) {
break;
}
}
if(!s2[j]) {
if(kt < 1000) {
v[kt] = i - l;
}
kt++;
}
}
hT -= dig(s1[i - l]) * Ap;
hT = hT % MOD;
if(hT < 0) hT += MOD;
}
g << kt << '\n';
for(i = 0; i < min(1000, kt); i++) {
g << v[i] << ' ';
}
if(kt) g << '\n';
}
g.close();
return 0;
}