Pagini recente » Cod sursa (job #2910328) | Cod sursa (job #2851419) | Cod sursa (job #2114370) | Cod sursa (job #2135298) | Cod sursa (job #2618742)
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string.h>
#define MAX 2000001
#define MOD 100021
#define d 256
int main()
{
FILE *in = fopen("strmatch.in", "r");
FILE *out = fopen("strmatch.out", "w");
char *subsir = (char *)malloc(MAX * sizeof(char));
char *sir = (char *)malloc(MAX * sizeof(char));
fscanf(in, "%s%s", subsir, sir);
int m = strlen(subsir);
int n = strlen(sir);
int h_sir = 0;
int h_subsir = 0;
int h = 1;
std::vector<int> aparitii;
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)
aparitii.push_back(i);
}
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;
}
}
fprintf(out, "%lu\n", aparitii.size());
for (int i = 0; i < aparitii.size(); i++)
{
fprintf(out, "%d ", aparitii[i]);
}
fclose(in);
fclose(out);
return 0;
}