Cod sursa(job #2259668)

Utilizator andrei_diaconu11Andrei C. Diaconu andrei_diaconu11 Data 13 octombrie 2018 16:44:28
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 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';
  for(auto e : sol)
    fo << e << ' ';
  fi.close();
  fo.close();
  return 0;
}