Pagini recente » Cod sursa (job #1223536) | Cod sursa (job #157379) | Cod sursa (job #358677) | Cod sursa (job #1322004) | Cod sursa (job #1442804)
using namespace std;
/*
#include <fstream>
#include <string.h>
ifstream f("strmatch.in");
ofstream g("strmatch.out");
*/
#include <fstream>
#include <string.h>
#define NMax 2000005
FILE *f=fopen ("strmatch.in","r");
FILE *g=fopen ("strmatch.out", "w");
int M,N;
char A[NMax],B[NMax];
int pi[NMax],pos[1024];
void make_prefix()
{
int q=0,i;
for(pi[1]=0,i=2;i<=M;i++)
{
while(q&&A[q+1]!=A[i])
q=pi[q];
if(A[q+1]==A[i])
++q;
pi[i]=q;
}
}
int main ()
{
int i,q=0,n=0;
fscanf(f,"%s",A);
fscanf(f,"%s",B);
M=strlen(A);
N=strlen(B);
for(i=M;i>=1;i--)A[i]=A[i-1];
A[0]=' ';
for(i=N;i>=1;i--)B[i]=B[i-1];
B[0]=' ';
make_prefix();
for(i=1; i<=N; i++)
{
while(q&&A[q+1]!=B[i])
q=pi[q];
if(A[q+1]==B[i])
++q;
if(q==M)
{
q=pi[M];
n++;
if(n<=1000)
pos[n]=i-M;
}
}
fprintf(g,"%d\n",n);
if(n<=1000) for(i=1; i<=n; i++) fprintf(g,"%d ",pos[i]);
else for(i=1; i<=1000; i++) fprintf(g,"%d ",pos[i]);
return 0;
}