Cod sursa(job #3143637)

Utilizator matyaskrizbaiKrizbai Matyas matyaskrizbai Data 1 august 2023 09:49:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

void constr(vector<int>& lps, string w, int m) {
  int i=0, j=1;
  lps[0]=0;
  while(j<m) {
    if(w[i]==w[j]) {
        i++;
        lps[j]=i;
        j++;
    }
    else {
      if(i!=0)
        i=lps[i-1];
      else {
        lps[i]=0;
        j++;
      }
    }
  }
}

void KMP(string w, string s) {
  int m=w.size();
  int n=s.size();
  vector<int> lps(m);
  constr(lps, w, m);

  int i=0, j=0;
  vector<int> ans;
  while((n-i)>=(m-j)) {
    if(w[j]==s[i]) {
      i++;
      j++;
    }
    if(j==m) {
      ans.push_back(i-j);
      j=lps[j-1];
    }
    else if(i<n && w[j]!=s[i]) {
      if(j!=0)
        j=lps[j-1];
      else
        i++;
    }
  }
  int k=ans.size();
  fout << k << '\n';
  if(k>1000)
    k=1000;
  for(int i=0; i<k; i++)
    fout << ans[i] << ' ';
}

int main() {
  string s, w;
  getline(fin, w);
  getline(fin, s);
  KMP(w, s); 
  return 0;
}