Pagini recente » Cod sursa (job #3207575) | Cod sursa (job #32183) | Cod sursa (job #2940136) | Cod sursa (job #2500619) | Cod sursa (job #2056605)
#include <iostream>
#include <fstream>
#include <string.h>
#define Nmax 2000005
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char N[Nmax], H[Nmax];
int rsp[Nmax];
int S[Nmax], f, n, h, cnt;
int main()
{
fin >> N + 1;
n = strlen(N + 1);
S[0] = -1;
S[1] = 0;
for (int i = 2; i <= n; i++)
{
int k = i - 1;
char c = N[i];
while (S[k] != -1 && N[S[k] + 1] != c)
k = S[k];
S[i] = S[k] + 1;
}
fin >> H + 1;
h = strlen(H + 1);
f = 0;
for (int i = 1; i <= h; i++)
{
while (f && N[f + 1] != H[i])
f = S[f];
if (N[f + 1] == H[i])
f++;
if (f == n)
{
f = S[f];
cnt++;
if (cnt <= 1000)
rsp[cnt] = i - n;
}
}
fout << cnt << '\n';
for (int i = 1; i <= min(cnt, 1000); i++)
fout << rsp[i] << " ";
return 0;
}