Cod sursa(job #2305079)

Utilizator isav_costinVlad Costin Andrei isav_costin Data 19 decembrie 2018 01:00:43
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>

const int MAXN=2000000;
const int END=1000;

using namespace std;

string a, b;
vector<int> ans;
int pi[MAXN+5];

int main()
{
  freopen( "strmatch.in", "r", stdin );
  freopen( "strmatch.out", "w", stdout );

  int p;

  cin>>a>>b;

  int k=0;

  for( int i=1;i<a.size();i++ )
  {
    while( k>0 && a[k]!=a[i] )
      k=pi[k-1];

    if( a[k]==a[i] )
      k++;

    pi[i]=k;
  }

  k=0;

  for( int i=0;i<b.size();i++ )
  {
    while( k>0 && a[k]!=b[i] )
      k=pi[k-1];

    if( a[k]==b[i] )
      k++;

    if( k==a.size() )
    {
      if( ans.size()<END )
        ans.push_back(i-a.size()+1);
      else
        ans.push_back(-1);
    }
  }

  cout<<ans.size()<<endl;

  for( vector<int>::iterator it=ans.begin();it!=ans.end() && *it!=-1;it++ )
    cout<<*it<<' ';

  return 0;
}