Pagini recente » Cod sursa (job #21990) | Cod sursa (job #1794563) | Cod sursa (job #741956) | Cod sursa (job #660535) | Cod sursa (job #1769265)
#include<stdio.h>
using namespace std;
char A[2000005],B[2000005];
int LPS[2000005];
int sol[1000001];
int nrsol;
void lps()
{
LPS[0]=0;
int len=0;
int i=0;
int M=0;
while(B[i])
{
M++;
i++;
}
i=1;
while(i<M)
{
if(B[i]==B[len])
{
len++;
LPS[i]=len;
i++;
}
else if(len!=0)
{
len=LPS[len-1];
}
else
{
LPS[i]=0;
i++;
}
}
//for(int i=0;i<M;i++) printf("%d ",LPS[i]);
}
void KMP()
{
int i=0;
int j=0;
int N=0;
int M=0;
while(A[i])
{
N++;
i++;
}
i=0;
while(B[i])
{
M++;
i++;
}
i=0;
while(i<N)
{
if(A[i]==B[j])
{
i++;
j++;
}
if(j==M)
{
sol[nrsol++]=i-j;
j=LPS[j-1];
}
else if(i<N&&A[i]!=B[j])
{
if(j!=0) j=LPS[j-1];
else i++;
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",&B);
scanf("%s",&A);
lps();
KMP();
if(nrsol>1000000) nrsol=1000000;
printf("%d\n",nrsol);
for(int i=0;i<nrsol;i++) printf("%d ",sol[i]);
}