Cod sursa(job #2006483)

Utilizator costi2Radu Canu costi2 Data 29 iulie 2017 22:52:46
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 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[10001];
  int nr = 0;
  int DIM1 = pattern.length();
  int DIM2 = text.length();
  int i =0;int j  = 0;
  for(int i = 1; i < DIM1;)
  {
    if(pattern[i] == pattern[j])
    {
      j++;
      vec[i] = j;
      i++;
    }
    else
    {
      if(j != 0)
        j = vec[j-1];
      else
      {
        vec[i] = 0;
        i++;
      }
    }
  }
  i = 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 DIM3 = positions.size();
  if(DIM3 > 1000)
    DIM3 = 1000;
  for( int i = 0; i < DIM3 ; i++)
    out << positions[i] << ' ';
//  delete[] vec;
  return 0;
}