Cod sursa(job #3148009)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 28 august 2023 20:45:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 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;
}

/*
KMP implementation.

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

Notice how this function is computed only on the pattern. Based on these values,
we determine the longest prefix of the pattern occuring as suffix at each 
position in the text.
*/