Pagini recente » Cod sursa (job #496165) | Cod sursa (job #1871986) | Cod sursa (job #576624) | Cod sursa (job #470546) | Cod sursa (job #1496897)
#include<fstream>
#include<string.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
#define MAX 2000001
char A[MAX], B[MAX];
int prefix[MAX],v[1001],N=0;
void make_prefix()
{
int l = strlen(A);
int i = 0,j=1;
while (j < l)
{
if (A[i] == A[j])
prefix[j++] = ++i;
else if (i>0)
i = prefix[i - 1];
else
prefix[j++] = i;
}
}
void KMP()
{
int l_A = strlen(A);
int l_B = strlen(B);
make_prefix();
int i = 0, j = 0;
while (j < l_B)
{
if (A[i] == B[j])
++i, ++j;
else if (i>0)
i = prefix[i - 1];
else
++j;
if (i == l_A)
{
++N;
if (N <= 1000)
v[N] = j - l_A;
i = prefix[i - 1];
}
}
}
int main()
{
in >> A;
in >> B;
KMP();
out << N <<'\n';
for (int i = 1;i <= N && i <= 1000;++i)
out << v[i]<<" ";
return 0;
}