Pagini recente » Cod sursa (job #669127) | Cod sursa (job #223184) | Istoria paginii runda/huehuhue/clasament | Cod sursa (job #467380) | Cod sursa (job #2680773)
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <fstream>
#include <vector>
#include <stdio.h>
using namespace std;
#define min(a, b) ((a < b) ? a : b)
char A[2000005], B[2000005];
int pi[2000005];
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));
int j = 0;
int lasti = 0;
for (int i = 0; i < strlen(B); i++) {
lasti = i;
while (A[j] == B[i]) {
j++;
i++;
if (j == strlen(A) - 1 && A[j] == B[i]) {
nr++;
ind.push_back(lasti);
j = 0;
lasti = i;
}
}
if (j != 0)
j = pi[j] - 1;
}
printf("%d\n", nr);
for (int i = 0; i < min(ind.size(), 1000); i++) {
printf("%d ", ind[i]);
}
}