Pagini recente » Cod sursa (job #2507171) | Cod sursa (job #2972730) | Cod sursa (job #635396) | Cod sursa (job #2927243) | Cod sursa (job #2618754)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 200001
#define MOD 1000021
#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_sir = 0;
int h_subsir = 0;
int h = 1;
int nr = 0;
int aparitii[1000];
for (int i = 0; i < m - 1; i++)
{
h = (d * h) % MOD;
h_sir = (d * h_sir + sir[i]) % MOD;
h_subsir = (d * h_subsir + subsir[i]) % MOD;
}
h_sir = (d * h_sir + sir[m - 1]) % MOD;
h_subsir = (d * h_subsir + subsir[m - 1]) % MOD;
for (int i = 0; i <= n - m; i++)
{
if (h_sir == h_subsir)
{
int j;
for (j = 0; j < m; j++)
{
if (subsir[j] != sir[i + j])
break;
}
if (j == m)
{
if (nr < 1000)
aparitii[nr] = i;
nr++;
}
}
if (i != n - m)
{
h_sir = (d * (h_sir - h * sir[i]) + sir[i + m]) % MOD;
h_sir = h_sir < 0 ? h_sir + MOD : h_sir;
}
}
printf("%d\n", nr);
for (int i = 0; i < nr && i < 1000; i++)
{
printf("%d ", aparitii[i]);
}
fclose(in);
fclose(out);
return 0;
}