Pagini recente » Cod sursa (job #860072) | Cod sursa (job #2929494) | Cod sursa (job #2708442) | Cod sursa (job #1157827) | Cod sursa (job #489127)
Cod sursa(job #489127)
#include <stdio.h>
#include <string.h>
#define MOD 67867979
long i, val, val2, len1, len2, gpow, sol, v[2000010];
char s1[2000010], s2[2000010];
long put(long num) {
long p = 1;
for (long i = 1; i <= num; ++i) {
p *= 26;
if (p > MOD)
p %= MOD;
}
return p;
}
long test(long l1, long l2) {
long ok = 1;
for (long i = l1; i <= l2; ++i) {
if (s1[i - l1] != s2[i]) {
ok = 0;
break;
}
}
return ok;
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s", s1, s2);
len1 = strlen(s1);
for (i = 0; i < len1; ++i) {
val += put(len1 - i - 1) * (long)(s1[i] - 'A');
val2 += put(len1 - i - 1) * (long)(s2[i] - 'A');
if (val > MOD) val %= MOD;
if (val2 > MOD) val2 %= MOD;
}
gpow = put(len1 - 1);
if (val == val2) {
if (test(0, len1 - 1)) {
++sol;
v[sol] = 0;
} else {
while (1);
}
}
len2 = strlen(s2);
for (i = 0; i + len1 <= len2; ++i) {
val2 -= ((gpow * (long)(s2[i] - 'A')) % MOD);
val2 *= 26;
val2 += (long)(s2[i + len1] - 'A');
if (val == val2) {
if (test(i + 1, i + len1)) {
++sol;
v[sol] = i + 1;
} else {
while (1);
}
}
}
printf("%ld\n", sol);
for (i = 1; i <= sol && i <= 1000; ++i) {
printf("%ld ", v[i]);
}
printf("\n");
if( sol > 1000) while(1 );
//printf("%ld %ld\n", val, val2);
return 0;
}