Cod sursa(job #3148008)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 28 august 2023 20:42:10
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 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();
  //text = " " + text;
  m = text.size();
  vector<int> longestPrefix(n, 0);
  
  ind = 0;
  for (i = 1; i < n; i++) {
    while (ind != 0 && pattern[ind] != pattern[i]) {
      ind = longestPrefix[ind - 1];
    }
    
    if (pattern[ind] == pattern[i])
      ind++;
    longestPrefix[i] = ind;
  }
  
  ind = 0;
  for (i = 0; i < m; i++) {
    while (ind != 0 && pattern[ind] != text[i]) {
      ind = longestPrefix[ind - 1];
    }
    
    if (pattern[ind] == text[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].
*/