Pagini recente » Cod sursa (job #1456594) | Cod sursa (job #1132207) | Cod sursa (job #1874664) | Cod sursa (job #2531671) | Cod sursa (job #2618768)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 2000010
#define MOD1 100007
#define MOD2 100021
#define d 73
int main()
{
FILE *in = freopen("strmatch.in", "r", stdin);
FILE *out = freopen("strmatch.out", "w", stdout);
char *subsir = (char *)malloc(MAX * sizeof(char));
char *sir = (char *)malloc(MAX * sizeof(char));
char c;
int n = 0;
int m = 0;
while ((c = getchar()) != '\n')
{
subsir[m++] = c;
}
subsir[m] = 0;
while ((c = getchar()) != '\n' && c != EOF)
{
sir[n++] = c;
}
sir[n] = 0;
int h_sir1 = 0;
int h_subsir1 = 0;
int h_sir2 = 0;
int h_subsir2 = 0;
int h1 = 1;
int h2 = 1;
int nr = 0;
int aparitii[1000];
for (int i = 0; i < m - 1; i++)
{
h1 = (d * h1) % MOD1;
h2 = (d * h2) % MOD2;
h_sir1 = (d * h_sir1 + sir[i]) % MOD1;
h_subsir1 = (d * h_subsir1 + subsir[i]) % MOD1;
h_sir2 = (d * h_sir2 + sir[i]) % MOD2;
h_subsir2 = (d * h_subsir2 + subsir[i]) % MOD2;
}
h_sir1 = (d * h_sir1 + sir[m - 1]) % MOD1;
h_subsir1 = (d * h_subsir1 + subsir[m - 1]) % MOD1;
h_sir2 = (d * h_sir2 + sir[m - 1]) % MOD2;
h_subsir2 = (d * h_subsir2 + subsir[m - 1]) % MOD2;
for (int i = 0; i <= n - m; i++)
{
if (h_sir1 == h_subsir1 && h_sir2 == h_subsir2)
{
if (nr < 1000)
aparitii[nr] = i;
nr++;
}
if (i != n - m)
{
h_sir1 = (d * (h_sir1 - h1 * sir[i]) + sir[i + m]) % MOD1;
h_sir1 = h_sir1 < 0 ? h_sir1 + MOD1 : h_sir1;
h_sir2 = (d * (h_sir2 - h2 * sir[i]) + sir[i + m]) % MOD2;
h_sir2 = h_sir2 < 0 ? h_sir2 + MOD2 : h_sir2;
}
}
printf("%d\n", nr);
for (int i = 0; i < nr && i < 1000; i++)
{
printf("%d ", aparitii[i]);
}
fclose(in);
fclose(out);
return 0;
}