Pagini recente » Borderou de evaluare (job #1024465) | Borderou de evaluare (job #1519783) | Borderou de evaluare (job #1608047) | Borderou de evaluare (job #2895877) | Cod sursa (job #2412683)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
const int nmax = 2 * 1e6;
const int base = 75;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
unsigned long long a[1 + nmax], b[1 + nmax];
string s1, s2;
unsigned long long maxexp;
vector <int> sol;
void citire() {
in >> s1 >> s2;
}
void hasha() {
maxexp = 1;
for(int i = 0; i < s1.size(); i ++) {
if(i == 0) {
a[i] = (s1[i] - '0');
} else {
a[i] = a[i - 1] * base + (s1[i] - '0');
}
maxexp *= base;
}
}
void hashb() {
for(int i = 0; i < s2.size(); i ++) {
if(i == 0) {
b[i] = (s2[i] - '0');
} else {
b[i] = b[i - 1] * base + (s2[i] - '0');
}
}
}
void solve() {
hasha();
hashb();
int nsol = 0, n = s1.size();
for(int i = n - 1; i < s2.size(); i ++) {
unsigned long long cur;
if(i == n - 1) {
cur = b[i];
} else {
cur = b[i] - b[i - n] * maxexp;
}
if(cur == a[n - 1]) {
nsol ++;
if(sol.size() < 1000) {
sol.push_back(i + 1 - n);
}
}
}
out << nsol << '\n';
for(int i = 0; i < sol.size(); i ++) {
out << sol[i] << " ";
}
}
int main() {
citire();
solve();
return 0;
}