Cod sursa(job #3148003)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 28 august 2023 19:43:46
Problema Potrivirea sirurilor Scor 4
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

int n, m, i, j, ind, nrSol;
string text, pattern;
vector<int> positions;

int main() {
  fin >> pattern;
  fin >> text;
  n = pattern.size();
  m = text.size();
  
  ind = 0;
  vector<int> longestPrefix(m, 0);
  if (pattern[0] == text[0])
    longestPrefix[0] = 1;
  for (i = 1; i < m; i++) {
    while (ind != 0 && pattern[ind] != text[i]) {
      ind = longestPrefix[ind - 1];
    }
    
    if (pattern[ind] == text[i])
      ind++;
    longestPrefix[i] = ind;
    if (ind == n) {
      nrSol++;
      if (nrSol <= 1000)
        positions.push_back(i - n + 1);
    }
  }
  
  fout << nrSol << '\n';
  for (i = 0; i < positions.size(); i++)
    fout << positions[i] << " ";
    
  fin.close();
  fout.close();
  return 0;
}

/*
longestPrefix[i] = longest prefix of the pattern that is a suffix of text[0..i].
*/