Cod sursa(job #2067829)

Utilizator AlexandruLuchianov1Alex Luchianov AlexandruLuchianov1 Data 16 noiembrie 2017 21:09:51
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");

int const nmax = 2000000;
string s1, s2;
int pre[5 + 2 * nmax];

void computepre() {
  int i = 0;
  int j = 1;
  while(j < s1.size()) {
    if(s1[i] == s1[j]) {
      pre[j] = i + 1;
      i++;
      j++;
    } else {
      if(i == 0){
        pre[j] = 0;
        j++;
      } else  {
        i = pre[i - 1];
      }
    }
  }
}

int main() {
  in >> s1 >> s2;
  int initsize = s1.size();
  s1 += "*" + s2;
  computepre();

  vector<int> sol;
  int sum = 0;
  for(int i = initsize + 1; i < s1.size(); i++){
    if(pre[i] == initsize) {
      sum++;
      if(sum <= 1000)
        sol.push_back(i - initsize - initsize);
    }
  }
  out<< sum << '\n';
  sum = 0;
  for(int i = 0; i < sol.size(); i++) {
    out << sol[i] << " ";
  }
  return 0;
}