Pagini recente » Cod sursa (job #148430) | Cod sursa (job #48387) | Cod sursa (job #2423004) | Cod sursa (job #2373565) | Cod sursa (job #727930)
Cod sursa(job #727930)
// 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,sizeof(A),stdin);
fgets(B+1,sizeof(B),stdin);
for(i=1;A[i]>='A' && A[i]<='Z';i++);
N=--i;
for(i=1;B[i]>='A' && B[i]<='Z';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;
Interv[TOTAL]=i-N;
}
}
printf("%d \n",TOTAL);
for(i=1;i<=TOTAL;i++)
printf("%d ",Interv[i]);
return 0;
}