Pagini recente » Monitorul de evaluare | Istoria paginii utilizator/raluca10 | Atasamentele paginii Profil taxazan | Statistici Chirilov Cristian (KrossKD) | Cod sursa (job #2681656)
#include <stdio.h>
#include <vector>
#include <string.h>
using namespace std;
#define min(a, b) ((a < b) ? a : b)
#define NMax 2000001
char A[NMax], B[NMax];
int pi[NMax];
void MakePi(char* A, int leng) {
pi[0] = 0;
int lasti = 0;
int i = 1;
while (i < leng) {
if (A[lasti] == A[i]) {
pi[i++] = ++lasti;
}
else {
if (lasti != 0)
lasti = pi[lasti - 1];
else
pi[i++] = 0;
}
}
}
int main()
{
int nr = 0;
vector<int> ind;
freopen("strmatch.in", "rt", stdin);
freopen("strmatch.out", "wt", stdout);
scanf("%s %s", A, B);
MakePi(A, strlen(A));
if (strlen(A) > strlen(B))
{
printf("0\n");
return 0;
}
int j = 0;
int lasti = 0;
for (int i = 0; i < strlen(B); i++) {
if (A[j] == B[i]) {
j++;
}
else if(j!=0){
if (pi[j] > 0)
j = pi[j] - 1;
else
j = 0;
}
if (j == strlen(A)) {
nr++;
ind.push_back((i + 1) - strlen(A));
j = 0;
if (A[j] == B[i]) {
j++;
}
}
}
printf("%d\n", nr);
for (int i = 0; i < min(ind.size(), 1000); i++) {
printf("%d ", ind[i]);
}
return 0;
}