Pagini recente » Cod sursa (job #1507531) | Cod sursa (job #2529470) | Cod sursa (job #1965746) | Cod sursa (job #1820944) | Cod sursa (job #2137355)
#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; }
pattern = window = {0, 0};
for (int i = 0; i < n; ++i) {
pattern.a = (pattern.a * BASE + s1[i]) % MOD1;
pattern.b = (pattern.b * BASE + s1[i]) % MOD2; }
for (int i = 0; i < n; ++i) {
window.a = (window.a * BASE + s2[i]) % MOD1;
window.b = (window.b * BASE + s2[i]) % MOD2; }
if (pattern == window)
aps.push_back(0);
for (int i = 1; i + n - 1 < m; ++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; }