Cod sursa(job #2817474)

Utilizator victorzarzuZarzu Victor victorzarzu Data 13 decembrie 2021 18:41:25
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>
#define n_max 100001

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string a, b;
int lena, lenb;
int pi[2000001];

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

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

void solve()
{
  compute();
  vector<int> result;
  int number = 0, q = 0;
  
  for(int i = 1;i <= lenb;++i)
    {
      while(q && a[q + 1] != b[i])
        q = pi[q];
      if(a[q + 1] == b[i])
        q++;
      
      if(q == lena)
      {
        ++number;
        q = pi[q];
        if(number <= 1000)
          result.push_back(i - lena);
      }
    }
  g<<number<<'\n';
  for(int position : result)
    g<<position<<" ";
}

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