Pagini recente » Cod sursa (job #2244494) | Cod sursa (job #717799) | Cod sursa (job #1633029) | Cod sursa (job #823509) | Cod sursa (job #727935)
Cod sursa(job #727935)
// 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);
for(i=1;(A[i]>='A' && A[i]<='Z') || (A[i]>='a' && A[i]<='z') || (A[i]>='0' && A[i]<='9');i++);
N=--i;
for(i=1;(A[i]>='A' && A[i]<='Z') || (A[i]>='a' && A[i]<='z') || (A[i]>='0' && A[i]<='9');i++);
M=--i;
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;
}