Cod sursa(job #2259677)

Utilizator andrei_diaconu11Andrei C. Diaconu andrei_diaconu11 Data 13 octombrie 2018 16:50:08
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <bits/stdc++.h>

using namespace std;

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

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

int main()
{
  getline(fi, p);
  getline(fi, t);
  pi.push_back(-1);
  for(int i = 0; i < p.size(); i++){
    int j = pi[i];
    while(j != -1 && p[j] != p[i])
      j = pi[j];
    pi.push_back(j + 1);
  }
  int j = 0;
  for(int i = 0; i < t.size(); i++){
    if(t[i] == p[j])
      j++;
    else{
      j = pi[j];
      while(j != -1 && p[j] != t[i])
        j = pi[j];
      j++;
    }
    if(j == p.size()){
      sol.push_back(i + 1 - p.size());
      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;
}