Pagini recente » Cod sursa (job #2859272) | Cod sursa (job #498039) | Cod sursa (job #2310482) | Cod sursa (job #1571286) | Cod sursa (job #1523496)
#include <iostream>
#include <cstdio>
#include <string.h>
#define LMC 2000005
using namespace std;
void prefix();
char A[LMC],B[LMC];
int pi[LMC],M,N,n,rez[1005];
int main()
{
int i,q=0;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
A[0]=' ';
B[0]=' ';
cin >> (A+1) >> (B+1);
M=strlen(A)-1;
N=strlen(B)-1;
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;
}
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;
}
}