Cod sursa(job #2173744)

Utilizator andrei.arnautuAndi Arnautu andrei.arnautu Data 16 martie 2018 00:27:08
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
/**
  *  Worg
  *  Mar 16, 2018
  *  12:13:48 AM
  */
#include <vector>
#include <string>
#include <fstream>
#include <algorithm>

std::ifstream fin("strmatch.in"); std::ofstream fout("strmatch.out");

const int maxLen = 2 * (2000000 + 5);
const int maxPrint = 1000;

/*-------- Data --------*/
std::string a, b, s;
int z[maxLen];
/*-------- --------*/

void Z_Algorithm() {
  z[0] = (int)s.size();
  for(int i = 1, left = 0, right = 0; i < (int)s.size(); i++) {
    if(i <= right) {
      z[i] = std::min(z[i - left], right - i + 1);
    } else {
      z[i] = 0;
    }

    while(i + z[i] < (int)s.size() && s[z[i]] == s[i + z[i]]) {
      z[i]++;
    }

    if(i + z[i] - 1 > right) {
      left = i; right = i + z[i] - 1;
    }
  }
}

void GetSolution() {
  std::vector<int > sol;

  int n = (int)a.size(), m = (int)b.size();

  for(int i = n; i < n + m; i++) {
    if(z[i] >= n) {
      sol.push_back(i - n - 1);
      if((int)sol.size() == maxPrint) break;
    }
  }

  fout << (int)sol.size() << '\n';
  for(auto& itr : sol) {
    fout << itr << " ";
  }
}

int main() {
  fin >> a >> b; s = a + "$" + b;

  Z_Algorithm();

  GetSolution();

  return 0;
}