Cod sursa(job #2804980)

Utilizator victorzarzuZarzu Victor victorzarzu Data 21 noiembrie 2021 13:05:41
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>
#define oo 0x3f3f3f3f

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string a, b;
int pi[2000001], nr, a_len, b_len;
vector<int> rez;

void read()
{
  f>>a>>b;
  a_len = a.length(); b_len = b.length();
  a.insert(0, " ");
  b.insert(0, " ");
}

void prefixes()
{
  int q = 0;
  for(int i = 2;i <= a_len;++i)
    {
      while(q && a[q + 1] != a[i])
        q = pi[q];
      if(a[q + 1] == a[i])
        ++q;
      pi[i] = q;
    }
}

void solve()
{
  prefixes();
  int q = 0;
  for(int i = 1;i <= b_len;++i)
  {
    while(q && a[q + 1] != b[i])
      q = pi[q];
    if(a[q + 1] == b[i])
      ++q;

    if(q == a_len)
    {
      ++nr;
      q = pi[q];
      if(nr <= 1000)
        rez.push_back(i - a_len);
    }
  }
  g<<rez.size()<<'\n';
  for(auto it : rez)
    g<<it<<" ";
}


int main()
{
  read();
  solve();
  return 0;
}