Pagini recente » Cod sursa (job #372263) | Cod sursa (job #302562) | Cod sursa (job #2471128) | Cod sursa (job #1657040) | Cod sursa (job #1523569)
#include <iostream>
#include <cstdio>
#include <string.h>
#define LMC 2000005
using namespace std;
char A[LMC],B[LMC];
int pi[LMC],M,N,n,rez[1025];
void prefix()
{
int i,q=0;
pi[1]=0;
for(i=2;i<=M;i++)
{
while(q&&A[q+1]!=A[i])
q=pi[q];
if(A[q+1]==A[i]) q++;
pi[i]=q;
}
}
int main()
{
int i,q=0;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(A+1,sizeof(A),stdin);
fgets(B+1,sizeof(B),stdin);
A[0]=' ';
B[0]=' ';
M=strlen(A)-2;
N=strlen(B)-2;
prefix();
for(i=1;i<=N;i++)
{
while(q&&A[q+1]!=B[i])
q=pi[q];
if(A[q+1]==B[i]) q++;
if(q==M)
{
q=pi[M];
n++;
if(n<=1000)
rez[n]=i-M;
}
}
cout << n << endl;
for(i=1;i<=min(n,1000);i++) cout << rez[i] << " ";
return 0;
}