Pagini recente » Istoria paginii utilizator/contuti | Diferente pentru problema/parola intre reviziile 12 si 13 | Cod sursa (job #793026)
Cod sursa(job #793026)
#include <cstdio>
#include <cstring>
#define lungimeMax 2000010
using namespace std;
char A[lungimeMax];
char B[lungimeMax];
int prefix[lungimeMax];
int lungimeA;
int lungimeB;
int afisare[1000];
int lungimeAfisare;
void Prefix(){
int pos = 0;
for (int i = 2; i <= lungimeA; ++ i){
while (pos && A[i] != A[pos + 1]){
pos = prefix[pos];
}
if (A[i] == A[pos + 1]){
pos ++;
}
prefix[i] = pos;
}
}
void Citire(){
gets(A + 1);
gets(B + 1);
lungimeA = strlen (A + 1);
lungimeB = strlen (B + 1);
}
void Kmp(){
int pos = 0;
for (int i = 1; i <= lungimeB; ++ i){
while (pos && B[i] != A[pos + 1]){
pos = prefix[pos];
}
if (B[i] == A[pos + 1]){
pos ++;
}
if (pos == lungimeA){
if (lungimeAfisare < 1000){
afisare[lungimeAfisare ++] = i - pos;
}
}
}
}
void Afisare(){
printf ("%d\n", lungimeAfisare);
for (int i = 0; i < lungimeAfisare; ++ i){
printf ("%d ", afisare[i]);
}
}
int main()
{
freopen ("strmatch.in", "r", stdin);
freopen ("strmatch.out", "w", stdout);
Citire();
Prefix();
Kmp();
Afisare();
return 0;
}