Pagini recente » Cod sursa (job #2538796) | Cod sursa (job #1904291) | Cod sursa (job #1936062) | Cod sursa (job #1386822) | Cod sursa (job #489130)
Cod sursa(job #489130)
#include <stdio.h>
#include <string.h>
#define MOD 32103109
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 *= 62;
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;
}
void fa(char *a, int len)
{
for( int i = 0; i < len; ++i)
{
if ('0' <= a[i] && a[i] <= '9') a[ i ] -='0';
if ('a' <= a[i] && a[i] <= 'z') a[ i ] -='a' - 10;
if ('A' <= a[i] && a[i] <= 'Z') a[ i ] -='A' - 36;
}
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s", s1, s2);
len1 = strlen(s1);
len2 = strlen(s2);
fa( s1 , strlen(s1));
fa( s2 , strlen(s2));
for (i = 0; i < len1; ++i) {
val = val * 62 + s1[ i ];
val2 = val2 * 62 + s2[ i ];
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);
}
}
for (i = 0; i + len1 < len2; ++i) {
val2 -= (gpow * s2[i]) % MOD;
if( val2 < 0) val2 += MOD;
val2 *= 62;
val2 += s2[ i + len1 ];
val2 %= MOD;
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;
}