Pagini recente » Cod sursa (job #3363156) | Cod sursa (job #3363168) | Cod sursa (job #3363208) | Cod sursa (job #3363140) | Cod sursa (job #3363172)
#include <bits/stdc++.h>
#define BAZA 67
#define MOD 1000000007
#define MAXL 2000000
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int H[MAXL + 1], B[MAXL + 1];
vector <int> afis;
int putere(int a, int n){
int t;
if(n == 0){
return 1;
}
if(n % 2 == 1){
return (long long)putere(a, n - 1) * a % MOD;
}
t = putere(a, n / 2);
return (long long)t * t % MOD;
}
int t(char ch){
int rez;
if('0' <= ch && ch <= '9'){
rez = ch + 1;
}else if('a' <= ch && ch <= 'z'){
rez = ch - 'a' + 11;
}else if('A' <= ch && ch <= 'Z'){
rez = ch - 'A' + 37;
}
return rez;
}
int inv_mod(int x){
return putere(x, MOD - 2);
}
int getHash(int st, int dr){
return ((long long)(H[dr] - H[st - 1] + MOD) * inv_mod(B[st])) % MOD;
}
int main()
{
int Hmic, p, cnt, i;
string S1, S2;
fin >> S1 >> S2;
Hmic = 0;
p = 1;
for(i = 0; i < S1.size(); i++){
Hmic = (Hmic + (long long)p * t(S1[i])) % MOD;
p = ((long long)p * BAZA) % MOD;
}
p = 1;
for(i = 0; i < S2.size(); i++){
H[i] = (H[i - 1] + ((long long)p * t(S2[i]) % MOD)) % MOD;
// printf("p = %d, H[%d] = %d\n", (long long)p * t(S2[i]), i, H[i]);
B[i] = p;
p = ((long long)p * BAZA) % MOD;
}
cnt = 0;
for(i = S1.size() - 1; i < S2.size(); i++){
// printf("Hmic = %d, H = %d, st = %d dr = %d %d\n", Hmic, getHash(i - S1.size() + 1, i), i - S1.size() + 1, i, H[i]);
if(getHash(i - S1.size() + 1, i) == Hmic){
cnt++;
if(cnt <= 1000){
afis.push_back(i - S1.size());
}
}
}
fout << cnt << "\n";
sort(afis.begin(), afis.end());
for(i = 0; i < afis.size(); i++){
fout << afis[i] + 1<< " ";
}
fout << "\n";
return 0;
}