Pagini recente » Istoria paginii runda/wunderbareswanker/clasament | Cod sursa (job #2624666) | Cod sursa (job #1523355) | Istoria paginii runda/succes_1/clasament | Cod sursa (job #1082805)
#include <string.h>
#include <stdio.h>
#define modul1 100007
#define modul2 100021
#define maxim 2000001
#define x 73
char A[maxim], B[maxim];
int n, m;
int hash_nr1, hash_nr2, x1, x2;
char match[maxim];
int main()
{
freopen("strmatch.in", "rt", stdin);
freopen("strmatch.out", "wt", stdout);
scanf("%s %s", A, B);
n = strlen(A);
m = strlen(B);
x1 = x2 = 1;
hash_nr1 = hash_nr2 = 0;
for (int i = 0; i < n; i++)
{
hash_nr1 = (hash_nr1 * x + A[i]) % modul1;
hash_nr2 = (hash_nr2 * x + A[i]) % modul2;
if (i != 0)
{
x1 = (x1 * x) % modul1;
x2 = (x2 * x) % modul2;
}
}
if (n > m)
{
printf("0\n");
return 0;
}
int hash1 = 0, hash2 = 0;
for (int i = 0; i < n; i++)
{
hash1 = (hash1 * x + B[i]) % modul1;
hash2 = (hash2 * x + B[i]) % modul2;
}
int Nr = 0;
if (hash1 == hash_nr1 && hash2 == hash_nr2)
{
match[0] = 1;
Nr++;
}
for (int i = n; i < m; i++)
{
hash1 = ((hash1 - (B[i - n] * x1) % modul1 + modul1) * x + B[i]) % modul1;
hash2 = ((hash2 - (B[i - n] * x2) % modul2 + modul2) * x + B[i]) % modul2;
if (hash1 == hash_nr1 && hash2 == hash_nr2)
{
match[ i - n + 1 ] = 1;
Nr++;
}
}
printf("%d\n", Nr);
Nr = 0;
for (int i = 0; i < m && Nr < 1000; i++)
if (match[i])
{
Nr++;
printf("%d ", i);
}
printf("\n");
return 0;
}