Pagini recente » Cod sursa (job #3182780) | Cod sursa (job #1538723) | Cod sursa (job #3188282) | Cod sursa (job #2560264) | Cod sursa (job #2807272)
#include <iostream>
#include <cstring>
#include <fstream>
using namespace std;
const int NMAX = 2000000;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s[2 * NMAX], aux[NMAX], ch;
int z[2 * NMAX];
int pos[1000];
void initZ(char s[], int z[])
{
int len = strlen(s), l = 0, r = 0;
z[0] = 0;
for (int i = 1; i < len; i++)
{
if (r <= i)
z[i] = 0;
else
z[i] = min(z[i - l], r - i + 1);
while (i + z[i] < len && s[z[i]] == s[i + z[i]])
z[i]++;
if (r < i + z[i] - 1)
{
l = i;
r = i + z[i];
}
}
}
int main()
{
int nrap, j, len1, len2, i;
fin >> aux;
len1 = strlen(aux);
for (j = 0; j < len1; j++)
s[j] = aux[j];
ch = fin.get();
fin >> aux;
len2 = strlen(aux);
for (i = 0, j = len1; j < len1 + len2; j++, i++)
s[j] = aux[i];
initZ(s, z);
nrap = 0;
for (j = len1; j < len2 + len1; j++)
if (z[j] >= len1)
{
if (nrap < 1000)
pos[nrap] = j - len1;
nrap++;
}
fout << nrap << '\n';
for (j = 0; j < min(nrap, 1000); j++)
fout << pos[j] << " ";
return 0;
}