Pagini recente » Cod sursa (job #925519) | Cod sursa (job #1122839) | Cod sursa (job #794230) | Cod sursa (job #729879) | Cod sursa (job #659220)
Cod sursa(job #659220)
#include<stdio.h>
#include<fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define MaxN 2000100
#define Max1000 1010
int nr,Pi[MaxN],C[Max1000];
char A[MaxN],B[MaxN];
void Prefix(void)
{
int k = -1;
Pi[0] = -1;
for(int i=1;A[i];i++)
{
for(;k > -1 && A[k+1] != A[i];k = Pi[k]);
if(A[k+1] == A[i]) ++ k;
Pi[i] = k;
}
}
void KMP(void)
{
int q = -1;
for(int i=0;B[i];i++)
{
for(;q > -1 && A[q+1] != B[i];q = Pi[q]);
if(A[q+1] == B[i]) ++q;
if(!A[q+1])
{
if(C[0] < 1001)
C[++C[0]] = i-q;
++ nr;
q = Pi[q];
}
}
}
int main()
{
f >> A >> B;
Prefix();
KMP();
g << nr << "\n";
for(int i=1;i<=C[0];i++)
g << C[i] << " ";
return 0;
}