Pagini recente » Cod sursa (job #2371941) | Cod sursa (job #44508) | Cod sursa (job #1932999) | Cod sursa (job #2049489) | Cod sursa (job #186558)
Cod sursa(job #186558)
using namespace std;
#include <cstdio>
#include <cstring>
#define Lmax 2000001
int nr,L1,L2;
char A[Lmax],B[Lmax];
int T[Lmax];
int P[1001];
void buildT()
{
int i,k;
T[0]=-1;
k=-1;
for (i=1; i<L1; ++i)
{
while (A[k+1] != A[i] && k>=0)
k=T[k];
if (A[k+1] == A[i]) ++k;
T[i]=k;
}
}
void kmp()
{
int i,k;
k=-1;
for (i=0; i<L2; ++i)
{
while (A[k+1] != B[i] && k>=0)
k=T[k];
if (A[k+1] == B[i]) ++k;
if (k==L1-1)
if (nr<1000)
P[nr++]=i-L1+1;
else ++nr;
}
}
int main()
{
int i;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s\n",&A);
scanf("%s\n",&B);
L1=strlen(A);
L2=strlen(B);
buildT();
kmp();
printf("%d\n",nr);
for (i=0; i<nr && i<1000; ++i)
printf("%d ",P[i]);
fclose(stdout);
return 0;
}