Pagini recente » Cod sursa (job #1728201) | Cod sursa (job #2687526) | Cod sursa (job #1351025) | Cod sursa (job #3215736) | Cod sursa (job #1523552)
#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[1025];
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;
if(n>=1000) n=1000;
for(i=1;i<=n;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;
}
}