Pagini recente » Cod sursa (job #2897515) | Cod sursa (job #1017356) | Cod sursa (job #2524049) | Cod sursa (job #735863) | Cod sursa (job #1218725)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
char A[2000005],B[2000005];
int N,M,P[2000005],ap;
vector<int> pos;
void read( void )
{
scanf("%s%s",A + 1, B + 1);
A[0] = B[0] = '#';
N = strlen(A + 1);
M = strlen(B + 1);
}
void make_prefix( void )
{
int i,q = 0;
for(int i = 2; i <= N; ++i)
{
while(q && A[i] != A[q+1])
q = P[q];
q += (A[i] == A[q+1]);
P[i] = q;
}
}
void make_match( void )
{
int i,q = 0;
for(int i = 1; i <= M; ++i)
{
while(q && B[i] != A[q + 1])
q = P[q];
q += (B[i] == A[q+1]);
if(q == N)
{
++ap;
if(pos.size() < 1000)
pos.push_back( i - N );
q = P[q];
}
}
}
void afish( void )
{
printf("%d\n",ap);
for(vector<int>::iterator it = pos.begin(); it != pos.end(); ++it)
printf("%d ",*it);
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
read();
make_prefix();
make_match();
afish();
return 0;
}