Pagini recente » Cod sursa (job #325436) | Cod sursa (job #757180) | Cod sursa (job #1251073) | Cod sursa (job #1491951) | Cod sursa (job #2681673)
#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, int pi[]) {
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);
int M = strlen(A), N = strlen(B);
MakePi(A, M, pi);
if (M > N)
{
{
printf("0\n");
return 0;
}
int j = 0;
int i = 0;
while (i < M) {
if (A[j] == B[i]) {
j++;
i++;
}
if (j == M) {
nr++;
ind.push_back(i - M);
j = pi[j - 1];
}
else if (i < M && A[j] != B[i]) {
if (j != 0)
j = pi[j - 1];
else
i++;
}
}
printf("%d\n", nr);
for (int i = 0; i < min(ind.size(), 1000); i++) {
printf("%d ", ind[i]);
}
return 0;
}