Cod sursa(job #2006382)

Utilizator costi2Radu Canu costi2 Data 29 iulie 2017 18:17:05
Problema Potrivirea sirurilor Scor 40
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 i = 1, j = 0;
    int *vec = new int[pattern.length()+1];
    vec[0] = 0;
    for(unsigned int i = 1; i < pattern.length();)
    {
      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 KMP(string text,string pattern,int poz ,int *vec)
{
  if(poz >= text.length())
  {
    return -1;
  }
  int j = 0,i = poz;
  int position = 0;
  while(j < pattern.length() && i < text.length())
  {
    if(text[i] == pattern[j])
    {
      i++;
      j++;
    }
    else
    {
      if(j != 0)
      {
        j = vec[j-1];
        position = i - j;
      }
      else
      {
        i++;
        position = i;
      }
    }
  }
  if(j == pattern.length())
  {
    positions.push_back(i - j);
    return i-j+1;
  }
  return -1;
}
int main()
{
  string text,pattern;
  in >> pattern;
  in >> text;
  int *vec = getArray(pattern);
  //for(unsigned int i = 0; i < s.length();i++)
    //cout<<vec[i]<<' ';
  int nr = -1;
  int rez = 0;
  while(rez != -1)
  {
    nr++;
    rez = KMP(text,pattern,rez,vec);
  }
  out << nr << '\n';
  for(int i = 0; i < positions.size(); i++)
    out << positions[i] << ' ';
  delete[] vec;
  return 0;
}