Pagini recente » Cod sursa (job #68062) | Cod sursa (job #269561) | Cod sursa (job #2266456) | Cod sursa (job #2818280) | Cod sursa (job #2884777)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define DIM 2000000
#define NMAX 1005
#define BAZA1 27
#define MOD1 10007
#define BAZA2 29
#define MOD2 666013
char a[DIM + 1], b[DIM + 1];
int lga, lgb;
int ans[DIM], k;
//algoritm de tipul fereastra glisanta;
static inline void Rubin_Karp() {
int v1, v2, p1, p2;
p1 = p2 = 1;
v1 = v2 = 0;
for(int i = 0; i < lga; i++) { //valoarea sirului a;
v1 = (v1 * BAZA1 + a[i]) % MOD1;
v2 = (v2 * BAZA2 + a[i]) % MOD2;
if(i != 1) {
p1 = (p1 * BAZA1) % MOD1;
p2 = (p2 * BAZA2) % MOD2;
}
}
int h1 = 0, h2 = 0;
for(int i = 0; i < lga; i++) {
h1 = (h1 * BAZA1 + b[i]) % MOD1; //valoarea primei subsecvente de lga din b;
h2 = (h2 * BAZA2 + b[i]) % MOD2;
}
if(v1 == h1 && v2 == h2) //daca primele secvente sunt la fel;
ans[++k] = 1;
for(int i = lga; i < lgb; i++) {
h1 = ((h1 - (b[i - lga] * p1) % MOD1 + MOD1) * BAZA1 + b[i]) % MOD1;
h2 = ((h2 - (b[i - lga] * p2) % MOD2 + MOD2) * BAZA2 + b[i]) % MOD2;
if(v1 == h1 && v2 == h2) {
k++;
if(k <= 1000)
ans[k] = i - lga + 1;
}
}
}
int main() {
fin >> a >> b;
lga = strlen(a);
lgb = strlen(b);
if(lga > lgb) {
fout << 0;
return 0;
}
Rubin_Karp();
fout << k << '\n';
int n = min(1000, k);
for(int i = 1; i <= n; i++)
fout << ans[i] << " ";
return 0;
}