Cod sursa(job #2304891)

Utilizator isav_costinVlad Costin Andrei isav_costin Data 18 decembrie 2018 19:26:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>

#define MAXN 2000000

using namespace std;

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

inline int maxim( int a, int b )
{
  if( a<b )
    a=b;

  return a;
}

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

  cin>>a>>b;

  int n=a.size();

  a=a+' '+b;

  int m=a.size();
  int st=0, dr=0;

  z[0]=1;

  for( int i=1;i<m;i++ )
  {
    z[i]=z[i-st];

    if( i+z[i]>=dr )
    {
      z[i]=maxim(0,dr-i);

      st=i;
      dr=i+z[i];
    }

    while( i+z[i]<m && a[z[i]]==a[i+z[i]] )
    {
      z[i]++;
      dr++;
    }

    if( z[i]==n )
      ans.push_back(i-n-1);
  }

  cout<<ans.size()<<'\n';

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

  return 0;
}