Pagini recente » Cod sursa (job #2241518) | Cod sursa (job #1330109) | Cod sursa (job #28353) | Cod sursa (job #3032824) | Cod sursa (job #1182042)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
class RollingHash {
public:
int A, MOD, pow, sum;
RollingHash(int A, int MOD, int N) : A(A), MOD(MOD), pow(1), sum(0) {
for (int i = 1; i <= N; ++i) pow = (pow * A) % MOD;
}
void add(char c) {
sum = (sum * A + c) % MOD;
}
void remove(char c) {
sum -= (pow * c) % MOD;
if (sum < 0) sum += MOD;
}
};
int hashString(int A, int MOD, string &s) { RollingHash h(A, MOD, s.length()); for (size_t i = 0; i < s.length(); ++i) h.add(s[i]); return h.sum; }
int main() {
//ifstream in("strmatch.in");
ifstream in("/home/bluetiger/Downloads/grader_test50.in");
ofstream out("strmatch.out");
string s, t;
getline(in, s);
getline(in, t);
vector<int> p;
int sh1 = hashString(67, 1000033, s);
int sh2 = hashString(79, 1000037, s);
RollingHash h1(67, 1000033, s.length());
RollingHash h2(79, 1000037, s.length());
for (size_t i = 0; i < t.length(); ++i) {
h1.add(t[i]); h2.add(t[i]);
if (i >= s.length()) h1.remove(t[i-s.length()]), h2.remove(t[i-s.length()]);
if ((h1.sum == sh1) && (h2.sum == sh2)) p.push_back(i - s.length() + 1);
}
// int pos = -1;
// while ((pos = t.find(s, pos + 1)) != -1)
// p.push_back(pos);
out << p.size() << endl;
size_t elems = min(p.size(), (size_t) 1000);
for (size_t i = 0; i < elems; ++i)
out << p[i] << " ";
return 0;
}