Pagini recente » Cod sursa (job #2196305) | Cod sursa (job #1972171) | Cod sursa (job #2637394) | Cod sursa (job #305761) | Cod sursa (job #632821)
Cod sursa(job #632821)
#include<cstdio>
#include<string.h>
#define N 2000005
#define MOD1 1299709
#define MOD2 1299721
#define MOD3 1299743
#define BASE 62
int contor;
char a[N];
int result[1005];
char b[N];
int ok;
int t, t2, t3;
int NA, NB;
int powb, powc, powd;
int str, str2, str3;
inline int convertNo(char z) {
if (z >='A' && z <= 'Z') {
return z - 'A';
}
else
if (z >='a' && z <= 'z') {
return z - 'a' + 26;
}
else
return z - '0' + 52;
}
void init() {
powb = 1;
powc = 1;
powd = 1;
for(int i = 1; i < NA; i++) {
powb = (powb * BASE) % MOD1;
powc = (powc * BASE) % MOD2;
powd = (powd * BASE) % MOD3;
}
return;
}
int minim(int a, int b) {
if(a < b) return a;
return b;
}
int checkeq(int i) {
ok = 1;
for(int j = i; j < i + NA; j++)
if(b[j] != a[j - i]) ok = 0;
if(ok == 1) {
contor++;
if (contor <= 1000)
result[contor] = i;
}
}
int main() {
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",&a);
scanf("%s",&b);
NA = strlen(a);
NB = strlen(b);
init();
for(int i = 0; i < NA; i++) {
t = (t * BASE + convertNo(a[i])) % MOD1;
t2 = (t2 * BASE + convertNo(a[i])) % MOD2;
t3 = (t3 * BASE + convertNo(a[i])) % MOD3;
str = (str * BASE + convertNo(b[i])) % MOD1;
str2 = (str2 * BASE + convertNo(b[i])) % MOD2;
str3 = (str3 * BASE + convertNo(b[i])) % MOD3;
}
if((str == t) && (str2 == t2) && (str3 == t3))
checkeq(0);
for(int i = 1; i <= NB - NA + 1; i++) {
str = ((str - (powb * convertNo(b[i-1])) % MOD1 + MOD1) * BASE + convertNo(b[i + NA - 1])) % MOD1;
str2 = ((str2 - (powc * convertNo(b[i-1])) % MOD2 + MOD2) * BASE + convertNo(b[i + NA - 1])) % MOD2;
str3 = ((str3 - (powd * convertNo(b[i-1])) % MOD3 + MOD3) * BASE + convertNo(b[i + NA - 1])) % MOD3;
if((str == t) && (str2 == t2) && (str3 == t3))
checkeq(i);
}
printf("%d\n",contor);
for(int i = 1; i <= minim(contor, 1000); i++)
printf("%d ", result[i]);
return 0;
}