Pagini recente » Cod sursa (job #1582750) | Cod sursa (job #1448833) | Cod sursa (job #2259963) | Diferente pentru runda/viata_periculoasa_pe_infoarena intre reviziile 9 si 8 | Cod sursa (job #1164895)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
char A[2000005],B[2000005]; /// 2 milioane Xd nu 1 mil my fault
int nrap,N,M;
int P[2000005];
vector<int> pos;
void read()
{
scanf("%s%s",A+1,B+1);
A[0] = B[0] = '#';
N = strlen(A) - 1;
M = strlen(B) - 1;
}
void make_prefix()
{
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()
{
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)
{
++nrap;
q = P[q];
if(pos.size() < 1000) pos.push_back(i-N);
}
}
}
void KMP()
{
make_prefix();
make_match();
}
void print()
{
printf("%d\n",nrap);
for(int i = 0; i <(int) pos.size(); ++i)
printf("%d ",pos[i]);
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
read();
KMP();
print();
return 0;
}