Cod sursa(job #2203676)

Utilizator Menage_a_011UPB Cheseli Neatu Popescu Menage_a_011 Data 12 mai 2018 21:13:44
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
// 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;
}