Pagini recente » Cod sursa (job #1505322) | Cod sursa (job #1500307) | Cod sursa (job #2523450) | Cod sursa (job #882200) | Cod sursa (job #995177)
Cod sursa(job #995177)
#include <stdio.h>
#include <string.h>
#define MAX 2000001
#define P 73
#define MOD1 100007
#define MOD2 100021
int nA[1000];
char str1[MAX], str2[MAX];
int main()
{
freopen("strmatch.in", "rt", stdin);
freopen("strmatch.out", "wt", stdout);
scanf("%s %s", str1, str2);
int a = strlen(str1), b = strlen(str2), nr = 0;
long long h1 = 0, h2 = 0, k1 = 0, k2 = 0, p1 = 1, p2 = 1;
for(int i = 0; i < a; i++)
{
h1 = (h1 * P + str1[i]) % MOD1;
h2 = (h2 * P + str1[i]) % MOD2;
if(i != 0)
{
p1 = (p1 * P) % MOD1;
p2 = (p2 * P) % MOD2;
}
}
for(int i = 0; i < a; i++)
{
k1 = (k1 * P + str2[i]) % MOD1;
k2 = (k2 * P + str2[i]) % MOD2;
}
if (h1 == k1 && h2 == k2)
nA[0] = 0, nr++;
for(int i = a; i < b; i++)
{
k1 = ((k1 - (str2[i - a] * p1) % MOD1 + MOD1) * P + str2[i]) % MOD1;
k2 = ((k2 - (str2[i - a] * p2) % MOD2 + MOD2) * P + str2[i]) % MOD2;
if (h1 == k1 && h2 == k2)
{
if(nr < 1000) nA[nr] = i - a + 1;
nr++;
}
}
printf("%d\n", nr);
if(nr >= 1000) nr = 1000;
for(int i = 0; i < nr; i++)
printf("%d ", nA[i]);
return 0;
}