Pagini recente » Cod sursa (job #260774) | Cod sursa (job #1414053) | Cod sursa (job #2540716) | Cod sursa (job #1500293) | Cod sursa (job #1881711)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int NMax = 2000001;
const int INF = 0x3f3f3f3f;
const int mod1 = 100007;
const int mod2 = 100021;
const int a = 73;
const int b = 7;
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 = 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;
}
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 < 1000){
T++;
ans.push_back(Y - 1);
}
g << T << '\n';
for(int i = 0; i < ans.size(); ++i){
g << ans[i] - X + 1 << ' ';
}
return 0;
}