Cod sursa(job #2276424)

Utilizator ZappaManIosif Adrian-Mihai ZappaMan Data 4 noiembrie 2018 18:34:12
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
typedef int ull;

inline  ull minim(ull a, ull b) {
   return (a < b) ? a : b;
}

#define NMAX 2000005

void make_prefix(string A, vector<ull> & pi) {
   int n = A.length();
   for (int i=2, q=0; i <= n; ++i) {
      for (; q != 0 && A[q] != A[i-1]; q = pi[q]);
      if (A[i-1] == A[q]) q++;
      pi[i] = q;
   }
}

int main(void) {
   int i, q = 0, n = 0;
   ifstream iff("strmatch.in");
   ofstream off("strmatch.out");
   string A,B;
   iff >> A >> B;
   vector<ull> pos;
   vector<ull> pi(A.length() + 1, 0);
   make_prefix(A, pi);
   for (i = 0, q=0; i < (int)B.length(); ++i) {
      for (;q!=0 && A[q] != B[i-1]; q=pi[q]);
      if (A[q] == B[i-1]) q++;
      if (q == (int)A.length()) {
         n++;
         if (n <= 1000) {
            pos.push_back(i - q);
         }
      }
   }
   off << n;
   if (pos.size()) {
      off << endl;
   }
   for (int i = 0; i < (int)pos.size(); ++i) {
      off << pos[i] << " ";
   }
   off.close();
}