Pagini recente » Cod sursa (job #985206) | Cod sursa (job #1048892) | Cod sursa (job #2390480) | Cod sursa (job #640145) | Cod sursa (job #2137404)
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 2000005, BASE = 131, MOD1 = 666013, MOD2 = 666019;
struct Hash {
int a, b; };
static bool operator == (const Hash &u, const Hash &v) {
return u.a == v.a && u.b == v.b; }
char s1[N], s2[N];
vector<int> aps;
Hash pattern, window;
int n, m;
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
i64 pwr1, pwr2;
gets(s1); n = strlen(s1);
gets(s2); m = strlen(s2);
pwr1 = pwr2 = 1;
for (int i = 1; i < n; ++i) {
pwr1 = pwr1 * BASE % MOD1;
pwr2 = pwr2 * BASE % MOD2; }
if (n > m) {
puts("0");
return 0; }
window = pattern = {0, 0};
for (int i = 0; i < n; i++) {
window.a = (window.a * BASE + s2[i]) % MOD1;
window.b = (window.b * BASE + s2[i]) % MOD2;
pattern.a = (pattern.a * BASE + s1[i]) % MOD1;
pattern.b = (pattern.b * BASE + s1[i]) % MOD2; }
if (window == pattern)
aps.push_back(0);
for (int i = 1; i <= m - n + 1; i++) {
window.a = (((window.a - pwr1 * s2[i - 1]) * BASE + s2[i + n - 1]) % MOD1 + MOD1) % MOD1;
window.b = (((window.b - pwr2 * s2[i - 1]) * BASE + s2[i + n - 1]) % MOD2 + MOD2) % MOD2;
if (pattern == window)
aps.push_back(i); }
printf("%d\n", aps.size());
for (int i = 0; i < min(1000, int(aps.size())); i++)
printf("%d ", aps[i]);
printf("\n");
return 0; }