Cod sursa(job #2482477)

Utilizator MihclerioVladimir Chim Mihclerio Data 28 octombrie 2019 12:53:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include<bits/stdc++.h>

#define all(s) s.begin(),s.end()
#define rc(x) return cout<<x<<endl,0
#define forn(i,n) for(int i=0;i<int(n);i++)

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

typedef long long ll;
typedef long double ld;

const int nmax=2e6+3;
const int mod=998244353;
const ll inf=0x3f3f3f3f3f3f3f3f;

using namespace std;

int p[nmax];

int main()
{
  freopen("strmatch.in","r",stdin);
  freopen("strmatch.out","w",stdout);
  ios_base::sync_with_stdio(0); cin.tie(0);
  string a,b;
  cin>>a>>b;
  int c=0;
  for(int i=1;i<a.size();i++)
  {
    while(a[i]!=a[c] && c>0) c=p[c-1];
    if(a[i]==a[c]) c++;
    p[i]=c;
  }
  int i=0,j=0;
  vector<int> sol;
  while(j<b.size())
  {
    if(a[i]!=b[j])
    {
      if(i) i=p[i-1]; else j++;
    } else
    {
      i++;
      j++;
    }
    if(i==a.size()) sol.pb(j-a.size());
  }
  cout<<sol.size()<<"\n";
  int n=sol.size();
  forn(i,min(n,1000)) cout<<sol[i]<<" ";
}