Pagini recente » Cod sursa (job #2746588) | Cod sursa (job #2532455) | Cod sursa (job #2760677) | Cod sursa (job #3259933) | Cod sursa (job #2142213)
#include <bits/stdc++.h>
#define NMAX 2000005
#define MOD1 1000003
#define MOD2 10003
#define base 73
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int main() {
int limit, N;
int power1 = 1, power2 = 1;
int strHash1 = 0, strHash2 = 0;
int patternHash1 = 0, patternHash2 = 0;
vector <int> sol;
string text, pattern;
fin >> pattern >> text;
N = pattern.size();
for (int i = 0; i < N; ++i) {
patternHash1 = (patternHash1 * base + pattern[i] * base) % MOD1;
patternHash2 = (patternHash2 * base + pattern[i] * base) % MOD2;
strHash1 = (strHash1 * base + text[i] * base) % MOD1;
strHash2 = (strHash2 * base + text[i] * base) % MOD2;
power1 = (power1 * base) % MOD1;
power2 = (power2 * base) % MOD2;
}
if (strHash1 == patternHash1 && strHash2 == patternHash2) {
sol.push_back(0);
}
for (int i = N; i < (int)text.size(); ++i) {
strHash1 = ((strHash1 - (power1 * text[i - N]) % MOD1 + MOD1) * base + text[i] * base) % MOD1;
strHash2 = ((strHash2 - (power2 * text[i - N]) % MOD2 + MOD2) * base + text[i] * base) % MOD2;
if (strHash1 == patternHash1 && strHash2 == patternHash2) {
sol.push_back(i - N + 1);
}
}
limit = min((int)sol.size(), 1000);
fout << sol.size() << '\n';
for (int i = 0; i < limit; ++i) {
fout << sol[i] << ' ';
}
return 0;
}