Cod sursa(job #2719319)

Utilizator victorzarzuZarzu Victor victorzarzu Data 9 martie 2021 19:25:22
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <bits/stdc++.h>
#define oo 0x3f3f3f3f

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

void Read()
{
  f>>a; n = a.length(); a.insert(0, " ");
  f>>b; m = b.length(); b.insert(0, " ");
}

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

void Solve()
{
  precompute();
  int q = 0;
  for(int i = 1;i <= m;++i)
  {
    while(q && a[q + 1] != b[i])
      q = pi[q];
    if(a[q + 1] == b[i])
      ++q;

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


int main()
{
  Read();
  Solve();
  return 0;
}