Pagini recente » Cod sursa (job #395998) | Cod sursa (job #253912) | Cod sursa (job #281907) | Cod sursa (job #2639990) | Cod sursa (job #1670099)
#include <iostream>
#include <string.h>
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n, m;
int prefix[2000005], pos[1005], nr;
char N[2000005], M[2000005];
int main()
{
f.getline(M+1, 2000002);
f.getline(N+1, 2000002);
n = strlen(N+1);
m = strlen(M+1);
int q = 0;
for(int i = 2; i <= m; i++)
{
while(q && M[q+1] != M[i]) q = prefix[q];
if(M[q+1] == M[i]) q++;
prefix[i] = q;
}
q = 0;
for(int i = 1; i <= n; i++)
{
while(q && M[q+1] != N[i]) q = prefix[q];
if(M[q+1] == N[i]) q++;
if(q == m)
{
nr++;
q = prefix[q];
if(nr <= 1000) pos[nr] = i-m;
}
}
g<<nr<<'\n';
nr = min(nr, 1000);
for(int i = 1; i <= nr; i++) g<<pos[i]<<' ';
g<<'\n';
return 0;
}