Cod sursa(job #1475419)

Utilizator salam1Florin Salam salam1 Data 24 august 2015 05:39:22
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int NMAX = 2000505;
const int LIM = 1000;
int n, m, pi[NMAX];
char A[NMAX], B[NMAX];

void read() {
  fgets(A + 1, NMAX, stdin);
  fgets(B + 1, NMAX, stdin);
  n = strlen(A + 1) - 1;
  m = strlen(B + 1) - 1;
}

void solve() {
  // compute prefix function
  for (int i = 2, q = 0; i <= n; i++) {
    while (q && A[q + 1] != A[i]) q = pi[q];
    if (A[q + 1] == A[i]) q++;
    pi[i] = q;
  }
  
  // compute matches
  int noSol = 0;
  vector<int> sol;
  for (int i = 1, q = 0; i <= m; i++) {
    while (q && A[q + 1] != B[i]) q = pi[q];
    if (A[q + 1] == B[i]) q++;
    
    if (q == n) {
      noSol++;
      if (noSol <= LIM)
        sol.push_back(i - n);
      q = pi[q];
    }
  }
  
  printf("%d\n", noSol);
  for (size_t i = 0; i < sol.size(); i++) {
    if (i > 0) printf(" ");
    printf("%d", sol[i]);
  }
  printf("\n");
}

int main() {
  freopen("strmatch.in", "r", stdin);
  freopen("strmatch.out", "w", stdout);
  
  read(); 
  solve();
  return 0;
}