Pagini recente » Cod sursa (job #606139) | Cod sursa (job #987023) | Cod sursa (job #1973021) | Cod sursa (job #1274677) | Cod sursa (job #2680778)
#include <iostream>
#include <fstream>
#include <vector>
#include <stdio.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));
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]);
}
}