Pagini recente » Cod sursa (job #1702886) | Cod sursa (job #2625763) | Istoria paginii runda/oji_2 | Cod sursa (job #2704686) | Cod sursa (job #659241)
Cod sursa(job #659241)
#include<stdio.h>
#include<fstream>
using namespace std;
FILE *f = fopen("strmatch.in","r");
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] == '\n')
{
if(C[0] < 1000)
C[++C[0]] = i-q;
++ nr;
q = Pi[q];
}
}
}
int main()
{
fgets(A,sizeof(A),f);
fgets(B,sizeof(B),f);
Prefix();
KMP();
g << nr << "\n";
for(int i=1;i<=C[0];i++)
g << C[i] << " ";
return 0;
}