Pagini recente » Cod sursa (job #1811757) | Cod sursa (job #999656) | Cod sursa (job #553175) | Cod sursa (job #1462304) | Cod sursa (job #912625)
Cod sursa(job #912625)
#include <fstream>
#include <cassert>
#include <vector>
#include <cstring>
//#include <iostream>
using namespace std;
static const int MOD = 666013, A = 52, MAXL = 2000009;
vector<int> v;
char s1[MAXL], s2[MAXL];
int dig(char c) {
int ans = 0;
assert(('A' <= c && c <= 'Z') || ('a' <= c && c <= 'z'));
if(c >= 'a') {
ans = (c - 'a') + 26;
}
else {
ans = c - 'A';
}
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.push_back(i - l);
}
kt++;
}
}
hT -= dig(s1[i - l]) * Ap;
hT = hT % MOD;
if(hT < 0) hT += MOD;
}
g << kt << '\n';
for(i = 0; i < (int)v.size(); i++) {
g << v[i] << ' ';
}
if(v.size()) g << '\n';
}
g.close();
return 0;
}