Pagini recente » Atasamentele paginii Profil adm159753 | Monitorul de evaluare | Autentificare | Borderou de evaluare (job #3046173) | Cod sursa (job #1167097)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int LMAX = 2000000+5;
void Read(),Solve(),Print();
int LA,LB,Nr_Potriviri;
char A[LMAX];
char B[LMAX];
int Pi[LMAX];
int Potriviri[1005];
void Prefix()
{
int i,q;
for(i = 2, q = 0; i <= LA; i++)
{
while(A[q+1] != A[i] && q) q = Pi[q];
if(A[q+1] == A[i]) q++;
Pi[i] = q;
}
}
void KMP()
{
int i,q;
for(i = 1, q = 0; i <= LB; i++)
{
while(A[q+1] != B[i] && q) q = Pi[q];
if(A[q+1] == B[i]) q++;
if(q == LA)
{
Nr_Potriviri++;
if(Nr_Potriviri <= 1000) Potriviri[Nr_Potriviri] = i - LA;
q = Pi[q];
}
}
}
int main()
{
Read();
Solve();
Print();
return 0;
}
void Read()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",A+1);
scanf("%s",B+1);
}
void Solve()
{
LA = strlen(A+1);
LB = strlen(B+1);
Prefix();
KMP();
}
void Print()
{
int i;
printf("%d\n",Nr_Potriviri);
for(i = 1; i <= min(1000,Nr_Potriviri); i++)
printf("%d ",Potriviri[i]);
}