Pagini recente » Cod sursa (job #613912) | Cod sursa (job #2299259) | Cod sursa (job #1639440) | Cod sursa (job #428908) | Cod sursa (job #1881690)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const ll NMax = 2000001;
const ll INF = 0x3f3f3f3f;
const ll mod1 = 666013;
const ll mod2 = 666041;
const ll a = 3;
const ll b = 10007;
char x[NMax],y[NMax];
ll hash1,hash2;
ll H1,H2;
vector<ll> ans;
int main()
{
f.getline(x,NMax);
f.getline(y,NMax);
ll X = strlen(x);
ll Y = strlen(y);
ll A = 1,B = 1;
for(ll i = X - 1; i >= 0; --i){
if(i == X - 1){
H1 = x[i];
H2 = x[i];
hash1 = y[i];
hash2 = y[i];
continue;
}
A *= a; B *= b; A %= mod1; B %= mod2;
H1 = H1 + A * x[i]; H1 %= mod1;
H2 = H2 + B * x[i]; H2 %= mod2;
hash1 = hash1 + A * y[i]; hash1 %= mod1;
hash2 = hash2 + B * y[i]; hash2 %= mod2;
}
for(ll i = X; i < Y; ++i){
if(hash1 == H1 && hash2 == H2){
ans.push_back(i - 1);
}
hash1 = (hash1 - (y[i - X] * A) % mod1 + mod1) % mod1;
hash1 = hash1 * a; hash1 %= mod1;
hash1 = hash1 + y[i]; hash1 %= mod1;
hash2 = (hash2 - (y[i - X] * B) % mod2 + mod2) % mod2;
hash2 = hash2 * b; hash2 %= mod2;
hash2 = hash2 + y[i]; hash2 %= mod2;
}
if(hash1 == H1 && hash2 == H2){
ans.push_back(Y - 1);
}
g << ans.size() << '\n';
for(ll i = 0; i < ans.size(); ++i){
g << ans[i] - X + 1 << ' ';
}
return 0;
}