Pagini recente » Cod sursa (job #2879020) | Cod sursa (job #1743194) | Cod sursa (job #2349690) | Cod sursa (job #2161323) | Cod sursa (job #727982)
Cod sursa(job #727982)
// KMP
// By C0$tume|
#include <cstdio>
#include <cstring>
#define in "strmatch.in"
#define out "strmatch.out"
#define _NMAX 2000005
#define minim( a , b ) ((a<b) ? a : b)
using namespace std;
char A[_NMAX],B[_NMAX];
int pi[_NMAX],M,N;
void prefix()
{
int i,q;
for(i=2,q=0;i<=N;i++)
{
while(q && A[i]!=A[q+1])
q=pi[q];
if(A[i]==A[q+1])
++q;
pi[i]=q;
}
}
int main()
{
int Interv[_NMAX];
int i,q,TOTAL=0;
freopen(in,"r",stdin);
freopen(out,"w",stdout);
fgets(A+1,_NMAX,stdin);
fgets(B+1,_NMAX,stdin);
N=strlen(A+1);
M=strlen(B+1);
--N;
--M;
prefix();
for(i=1,q=0;i<=M;i++)
{
while(q && A[q+1]!=B[i])
q=pi[q];
if(A[q+1]==B[i])
++q;
if(q==N)
{
++TOTAL;
if(TOTAL<=1000)
Interv[TOTAL]=i-N;
}
}
printf("%d \n",TOTAL);
if(TOTAL>1000)
TOTAL=1000;
for(i=1;i<=TOTAL;i++)
printf("%d ",Interv[i]);
return 0;
}