Pagini recente » Cod sursa (job #2707723) | Cod sursa (job #2874696) | Cod sursa (job #1076586) | Cod sursa (job #1560517) | Cod sursa (job #706119)
Cod sursa(job #706119)
#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
#define minim(a, b) ((a < b) ? a : b)
#define NMax 2000005
int M, N;
char A[NMax], B[NMax];
int pi[NMax];
vector<int>v;
void make_prefix()
{
int i,q=0;
for (i=2,pi[1]=0;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);
scanf("%s%s", &A, &B);
M=strlen(A);
N=strlen(B);
for(i=M;i;--i)
A[i]=A[i-1];
A[0]=' ';
for(i=N;i;--i)
B[i]=B[i-1];
B[0] = ' ';
make_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];
v.push_back((i-M));
}
}
printf("%d\n", v.size());
for(i=0;i<minim(v.size(),1000);++i)
printf("%d ", v[i]);
printf("\n");
return 0;
}