Pagini recente » Cod sursa (job #1630239) | Cod sursa (job #41856) | Cod sursa (job #1087046) | Cod sursa (job #1537743) | Cod sursa (job #1797744)
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
#define DIM 2000006
char A[DIM], B[DIM];
vector <int> fail, rezultate;
int main() {
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s", A);
scanf("%s", B);
int N = strlen(A);
fail.resize(N + 2);
int j;
fail[0] = j = -1;
for(int i = 0; i < N; ++i) {
while(j >= 0 && A[j] != A[i]) {
j = fail[j];
}
++j;
fail[i + 1] = j;
}
j = 0;
int M = strlen(B);
int total = 0;
rezultate.reserve(1002); // !
for(int i = 0; i < M; ++i) {
while(j >= 0 && A[j] != B[i]) {
j = fail[j];
}
++j;
if(j == N) {
++total;
if(total <= 1000) rezultate.push_back(i - N + 1);
j = fail[j];
}
}
cout << total << '\n';
for(int i = 0; i < total && i < 1000; ++i) {
cout << rezultate[i] << ' ';
}
cout << '\n';
return 0;
}