Pagini recente » Cod sursa (job #1292289) | Cod sursa (job #1682854) | Cod sursa (job #356670) | Cod sursa (job #837047) | Cod sursa (job #509519)
Cod sursa(job #509519)
#include <stdio.h>
#define MOD1 1000007
#define MOD2 1000013
#define SIGMA 127
#define NMAX 2000010
char S[NMAX];
int v[1024];
int n, m;
inline void mod(int &x, int MOD){
while( x < 0) x += MOD;
while( x >= MOD) x -= MOD;
}
int main(){
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
int hash1 = 0, hash2 = 0, put1 = 1, put2 = 1;
fgets(S, NMAX, stdin);
int lung = 0;
for(int i = 0; S[i] != '\n' && S[i]; ++i){
hash1 = (hash1 * SIGMA + S[i]) % MOD1;
hash2 = (hash2 * SIGMA + S[i] ) % MOD2;
if(i != 0) {
put1 = (put1 * SIGMA) % MOD1;
put2 = (put2 * SIGMA) % MOD2;
}
lung = i;
}
fgets(S, NMAX, stdin);
int h1 = 0, h2 = 0;
for(int i = 0; i <= lung && S[i] && S[i] != '\n'; ++i){
h1 = (h1 * SIGMA + S[i] ) % MOD1;
h2 = (h2 * SIGMA + S[i] ) % MOD2;
}
if(h1 == hash1 && hash2 == h2) v[++v[0]] = 0;
for(int i = lung + 1; S[i] && S[i] != '\n' ; ++i){
h1 = ((h1 - ((S[i-lung-1]) * put1) % MOD1 + MOD1) * SIGMA + S[i])%MOD1;
h2 = ((h2 - ((S[i-lung-1]) * put2) % MOD2 + MOD2) * SIGMA + S[i])%MOD2;
mod(h1, MOD1);
mod(h2, MOD2);
if(h1 == hash1 && h2 == hash2){
v[0]++;
if(v[0] <= 1000) v[v[0]] = i-lung;
}
}
printf("%d\n", v[0]);
for(int i = 1; i <= 1000 && i <= v[0]; ++i)
printf("%d ", v[i]);
printf("\n");
//printf("%d %d %d", '9', 'z', 'Z');
return 0;
}