Pagini recente » Cod sursa (job #1650047) | Cod sursa (job #1236947) | Cod sursa (job #2012855) | Cod sursa (job #2480995) | Cod sursa (job #1049930)
#include <stdio.h>
#include <cstring>
using namespace std;
const int strLEN=2000002;
char A[strLEN],B[strLEN];
int lps[strLEN-2];
int sol[strLEN-1];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(A,strLEN,stdin);
fgets(B,strLEN,stdin);
int nA=strlen(A)-1;
int nB=strlen(B)-1;
//longest prefix-suffix
memset(lps,-1,sizeof(lps));
int pos=-1;
for(int i=1;i<nA;++i)
{
while(pos>=0&&A[pos+1]!=A[i]) pos=lps[pos];
if(A[pos+1]==A[i]) ++pos;
lps[i]=pos;
}
pos=-1;
for(int i=0;i<nB;++i)
{
while(pos>=0&&B[i]!=A[pos+1]) pos=lps[pos];
if(B[i]==A[pos+1]) ++pos;
if(pos+1==nA)
{
sol[++sol[0]]=i-nA+1;
pos=lps[pos];
}
}
printf("%d\n",sol[0]);
for(int i=1;i<=sol[0]&&i<=1000;++i)
printf("%d ",sol[i]);
printf("\n");
return 0;
}