Cod sursa(job #1708807)

Utilizator UPB_Darius_Rares_SilviuPeace my pants UPB_Darius_Rares_Silviu Data 27 mai 2016 23:25:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <cstdio>
#include <cstring>
#include <vector>
#define Nmax 2000099
using namespace std;

int N, M, pi[Nmax];
char A[Nmax], B[Nmax];
vector<int> sol;

void prefix(char *A) {
    int q, N = strlen(A + 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;
    }

}
void kmp(char *A, char *B, vector<int> &sol) {
    int q, N, M;
    N = strlen(A + 1), M = strlen(B + 1);

    prefix(A);

    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 ];
      }
    }

}

int main() {
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    scanf("%s%s", A+1, B+1);

    kmp(A, B, sol);

    printf("%d\n", sol.size());

    int imax = min((int)sol.size(), 1000);
    for(int i = 0; i < imax; ++i) {
        printf("%d ", sol[i] - 1);
    }

    return 0;
}