Cod sursa(job #2259712)

Utilizator andrei_diaconu11Andrei C. Diaconu andrei_diaconu11 Data 13 octombrie 2018 17:44:33
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>

using namespace std;

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

string p, t;
vector <int> sol, pi;

inline int get_pi(char ch, int i){//construim automatul
  i = pi[i];
  while(i != -1 && p[i] != ch)
    i = pi[i];
  return i;
}

int main()
{
  getline(fi, p);
  getline(fi, t);
  pi.push_back(-1);
  for(int i = 0; i < p.size(); i++)
    pi.push_back(get_pi(p[i], i) + 1);
  int j = 0;
  for(int i = 0; i < t.size(); i++){
    if(t[i] != p[j])
      j = get_pi(t[i], j);
    j++;
    if(j == p.size()){
      sol.push_back(i + 1 - j);
      j = pi[j];
    }
  }
  fo << sol.size() << '\n';
  if(sol.size() <= 1000)
    for(auto e : sol)
      fo << e << ' ';
  else
    for(int i = 0; i < 1000; i++)
      fo << sol[i] << ' ';
  fi.close();
  fo.close();
  return 0;
}