Pagini recente » Cod sursa (job #3169909) | Cod sursa (job #3142551) | Cod sursa (job #3142375)
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
typedef long long ll;
typedef pair<int, int> pi;
int t, T;
ll MOD = 1e9 + 7;
ll p = 53;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string P, T;
f >> P >> T;
T = " " + T;
int n = T.size();
vector<ll> hash_prefixes(n, 0), power_p(n, 1);
for (int i = 1; i < n; i++)
power_p[i] = (power_p[i - 1] * p) % MOD;
for (int i = 1; i < n; i++) {
hash_prefixes[i] = (hash_prefixes[i - 1] + ((T[i] - 'a' + 1) * power_p[i]) % MOD) % MOD;
}
int hash_P = 0;
for (int i = 0; i < P.size(); i++) {
hash_P = (hash_P + ((P[i] - 'a' + 1) * power_p[i]) % MOD) % MOD;
}
int cnt = 0;
vector<int> ans;
for (int i = 1; i < n - P.size(); i++) {
int j = i + P.size() - 1;
int hash_substring = (hash_prefixes[j] - hash_prefixes[i - 1] + MOD) % MOD; // +MOD to avoid negative numbers
if (hash_substring == (MOD + (hash_P * power_p[i]) % MOD) % MOD) {
cnt++;
if (ans.size() < 1000) {
ans.pb(i - 1);
}
}
}
g << cnt << '\n';
for (int x : ans) g << x << ' ';
return 0;
}