Pagini recente » Cod sursa (job #98427) | Cod sursa (job #2919668) | Cod sursa (job #1709324) | Cod sursa (job #1775841) | Cod sursa (job #1904666)
#include <bits/stdc++.h>
#define NMax 200001
#define INF 0x3f3f3f3f
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int a = 73;
const int b = 7;
const int mod1 = 100007;
const int mod2 = 100021;
char X[NMax], Y[NMax];
int hash1, hash2;
int H1, H2;
vector<int> ans;
int main()
{
f.getline(X, NMax);
f.getline(Y, NMax);
int x = strlen(X);
int y = strlen(Y);
int A = 1, B = 1;
for(int 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 += A * X[i]; H1 %= mod1;
H2 += B * X[i]; H2 %= mod2;
hash1 += A * Y[i]; hash1 %= mod1;
hash2 += B * Y[i]; hash2 %= mod2;
}
int t = 0;
for(int i = x; i < y; ++i)
{
if(hash1 == H1 && hash2 == H2)
{
++t;
if(ans.size() < 1000)
ans.push_back(i - 1);
}
hash1 = (hash1 - (Y[i - x] * A) % mod1 + mod1) % mod1;
hash1 = hash1 * a;
hash1 = hash1 + Y[i];
hash1 %= mod1;
hash2 = (hash2 - (Y[i - x] * B) % mod2 + mod2) % mod2;
hash2 = hash2 * b;
hash2 = hash2 + Y[i];
hash2 %= mod2;
}
if(hash1 == H1 && hash2 == H2)
{
++t;
if(t < 1000)
ans.push_back(y - 1);
}
g << t << '\n';
for(int i = 0; i < ans.size(); ++i)
g << ans[i] - x + 1 << " ";
return 0;
}