Pagini recente » Cod sursa (job #710171) | Cod sursa (job #1306188) | Cod sursa (job #533258) | Cod sursa (job #2485694) | Cod sursa (job #434235)
Cod sursa(job #434235)
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define Nmax 2000005
#define Smax 1005
int N,K,pi[Nmax];
char A[Nmax],B[Nmax];
int sol[Smax],cnt;
void KMP()
{
int k=0;
for(int i=1;i<=N;++i)
{
while( k>0 && A[k+1]!=B[i])
k=pi[k];
if (A[k+1]==B[i])
++k;
if (k==K)
{
++cnt;
if (cnt <= 1000)
sol[cnt]=i-K;
}
}
}
void prefix()
{
int k=0;
for(int i=2;i<=K;++i)
{
while( k>0 && A[k+1]!=A[i])
k=pi[k];
if (A[k+1]==A[i])
++k;
pi[i]=k;
}
}
void init()
{
K=strlen(A);
for(int i=K;i;--i)
A[i]=A[i-1];
A[0]=' ';
N=strlen(B);
for(int i=N;i;--i)
B[i]=B[i-1];
B[0]=' ';
}
void afis()
{
printf("%d\n",cnt);
for(int i=1,M=min(cnt,1000);i<=M;++i)
printf("%d ",sol[i]);
printf("\n");
}
void cit()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",A);
scanf("%s",B);
}
int main()
{
cit();
init();
prefix();
KMP();
afis();
return 0;
}