Cod sursa(job #2396542)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 3 aprilie 2019 16:45:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

const int LGMAX = 2000005;

string A, p;
int lps[LGMAX];

vector <int> pos;

void Read()
{
  fin >> p >> A;

  fin.close();
}

void Do()
{
  if( p.size() > A.size() )
  {
    fout << 0 << '\n';

    return;
  }

  int len = 0;
  int sz = p.size();

  for( int i = 1; i < sz; ++i )
  {
    if( p[len] == p[i] ) lps[i] = ++len;
    else
      if( len > 0 )
      {
        len = lps[len - 1];
        --i;
      }

  }

  int i, j;

  i = j = 0;
  sz = A.size();

  while( i < sz )
  {
    if( p[j] == A[i] )
    {
      ++i;
      ++j;
    }

    if( j == p.size() )
    {
      pos.push_back( i - j );

      j = lps[j - 1];
    }
    else
      if( i < sz && p[j] != A[i] )
      {
        if( j > 0 ) j = lps[j - 1];
        else ++i;
      }
  }

  sz = min( 1000, (int)pos.size() );

  fout << pos.size() << '\n';

  for( int i = 0; i < sz; ++i )
    fout << pos[i] << ' ';
}

int main()
{
    Read();
    Do();

    return 0;
}