Cod sursa(job #2006479)

Utilizator costi2Radu Canu costi2 Data 29 iulie 2017 22:47:52
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

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

vector<int> positions;

int* getArray(string pattern)
{
    int  j = 0;
    int DIM = pattern.length();
    int *vec = new int[DIM+1];
    vec[0] = 0;
    for(int i = 1; i < DIM;)
    {
      if(pattern[i] == pattern[j])
      {
        j++;
        vec[i] = j;
        i++;
      }
      else
      {
        if(j != 0)
          j = vec[j-1];
        else
        {
          vec[i] = 0;
          i++;
        }
      }
    }
    return vec;
}

int main()
{
  string text,pattern;
  in >> pattern;
  in >> text;
  int *vec = getArray(pattern);
  int nr = 0;
  int DIM1 = pattern.length();
  int DIM2 = text.length();
  int i =0;int j  = 0;
  while(i < DIM2 )
  {
    if(text[i] == pattern[j])
    {
      i++;
      j++;
    }
    else
    {
      if(j != 0)
      {
        j = vec[j-1];
      }
      else
      {
        i++;
      }
    }
    if(j == DIM1)
    {
      if(nr < 1001)
        positions.push_back(i - j);
      i=i-j+1;
      nr++;
      j = 0;
    }
  }

  out << nr << '\n';
  int DIM = positions.size();
  if(DIM > 1000)
    DIM = 1000;
  for( int i = 0; i < DIM ; i++)
    out << positions[i] << ' ';
  delete[] vec;
  return 0;
}