Pagini recente » Cod sursa (job #1593062) | Cod sursa (job #2034585) | Cod sursa (job #2583560) | Cod sursa (job #1954169) | Cod sursa (job #3195147)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000005], b[2000005];
long long p = 1007, mod = 1000000007;
vector < int > res;
int ans;
long long hash_a, hash_curent;
long long hash_b[2000005]; /// sume partiale pt hash-urile lui b
long long pw[2000005];
int n, m;
int main()
{
f >> a >> b;
n = strlen(a); m = strlen(b);
/// creem puterile lui p
pw[0] = 1;
for (int i=1;i<m;i++) {
pw[i] = (pw[i-1]*p) % mod;
}
/// calculam hash-ul sirului a
for (int i=0;i<n;i++) {
hash_a = (hash_a + a[i] * pw[i]) % mod;
}
/// calculam hash-urile sirului b
hash_b[0] = b[0]; /// * pw[0];
for (int i=1;i<m;i++) {
hash_b[i] = (hash_b[i-1] + b[i] * pw[i]) % mod;
}
/// comparam hash-urile din b cu hash-ul lui a
for (int i=0;i<=m-n;i++) {
if (i==0) hash_curent = hash_b[i+n-1];
else hash_curent = (hash_b[i+n-1] - hash_b[i-1] + mod)% mod;
if ((hash_a * pw[i])%mod == hash_curent) {
ans++;
if (ans<=1000) {
res.push_back(i);
}
}
}
g << ans << '\n';
for (auto x:res) {
g << x << " ";
}
return 0;
}