Cod sursa(job #3242048)

Utilizator RosheRadutu Robert Roshe Data 8 septembrie 2024 11:50:09
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <string.h>

#define MAX 2000000
using namespace std;

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

int *createSubPatterns(string p){
  int *lps = (int*) malloc(p.length() * sizeof(int));
  int i = 1, j = 0;
  while(i < p.length()){
    if(p[i] == p[j]){
      j++;
      lps[i] = j;
      i++;
    }  
    else{
      if(j > 0){
        j = lps[j-1];
      }
      else{
        lps[i] = 0;
        i++;
      }
    }
  }
  return lps;
}

int main(){
      string p, s;
      vector<int> pos(1001);
      getline(in, p);
      getline(in, s);
      int* lps = createSubPatterns(p);
      /*
      for(int i = 0; i<p.length(); i++)
        cout << lps[i] << ", ";
      cout << endl;
      */
      int j = 0;
      int matches = 0;
      for(int i = 0; i<s.length(); i++){
        if(j == p.length()){
          pos[matches++] = i;
          j = lps[j-1]; // lps[j];
          if(matches == 1000)
            break;
        }
        if(s[i] == p[j]) j++;
        else if(j > 0){
          j = lps[j-1];
          i--;
        }
      }
      out << matches << endl;
      for(int i = 0; i<matches; i++)
        out << pos[i] - p.length() << " ";
}