Pagini recente » Cod sursa (job #2143247) | Cod sursa (job #2201432) | Cod sursa (job #143329) | Cod sursa (job #1845745) | Cod sursa (job #2203676)
// https://goo.gl/fBmFxu
#include <bits/stdc++.h>
using namespace std;
#define NMAX 20000009
#define USE_FILES "MLC"
#ifdef USE_FILES
#define cin fin
#define cout fout
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#endif
// number of tests from "in"
int test_cnt = 1;
void clean_test();
// your global variables are here
char A[NMAX], B[NMAX];
int pi[NMAX];
void KMP(const char A[NMAX], const char B[NMAX], int pi[NMAX], vector<int> &sol) {
int q, N, M;
N = strlen(A+1), M = strlen(B+1);
for (int i = 0; i <= N; i++) {
pi[i] = 0;
}
q = 0;
pi[1] = 0;
for(int i = 2; i <= N; ++i) {
while(q && A[q+1] != A[i]) q = pi[q];
if(A[q+1] == A[i]) ++q;
pi[i] = q;
}
q = 0;
for(int i = 1; i <= M; ++i) {
while(q && A[q+1] != B[i]) q = pi[q];
if(A[q+1] == B[i]) ++q;
if(q == N) {
sol.push_back(i-N+1);
q = pi[N];
}
}
}
// your solution is here
void solve() {
cin >> (A+1) >> (B+1) ;
vector<int> sol;
KMP(A, B, pi, sol);
int imax = min((int)sol.size(), 1000);
cout << imax << "\n";
for (int i = 0; i < imax; ++i) {
cout << (sol[i] - 1) << " ";
}
cout << "\n";
if (test_cnt > 0) {
clean_test();
}
}
void clean_test() {
// clean if needed
}
int main() {
// cin >> test_cnt;
while (test_cnt--) {
solve();
}
return 0;
}