Cod sursa(job #3242079)

Utilizator RosheRadutu Robert Roshe Data 8 septembrie 2024 16:06:52
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <string>

using namespace std;

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

void createLPS(string s, vector<int> &lps){
  int i = 1, j = 0;
  int n = s.length();
  while(i < n){
    if(s[i] == s[j]){
      j++;
      lps[i] = j; 
      i++;
    }
    else{
      if(j>0){
        j = lps[j-1];
      }
      else{
        lps[i] = 0;
        i++;
      }
    }
  }
}

int main(){
  string p, s;
  int spotted = 0;
  getline(in, p);
  getline(in, s);
  vector<int> pos(1000);
  vector<int> lps(p.length()); // pattern array 
  createLPS(p, lps);
  //Knuth Morris Pratt
  int i = 0, j = 0;
  while(i < s.length()){
    if(s[i] == p[j]){
      i++;
      j++;
    }
    if(j == p.length()){
      pos[spotted++] = i - j;
      if(spotted == 1000)
        break;
      j = lps[j-1];  
    }
    if(s[i] != p[j]){
      if(j == 0){
        i++;
      }
      else{
        j = lps[j-1];
      }
    }
  }
  out << spotted << endl;
  for(int i = 0; i<spotted; i++)
    out << pos[i] << " ";
}