Cod sursa(job #2811030)

Utilizator victorzarzuZarzu Victor victorzarzu Data 30 noiembrie 2021 21:53:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string a, b;
int len_a, len_b, number;
int prefix[2000001];
vector<int> result;

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

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

void solve()
{
  precompute();
  int q = 0;
  for(int i = 1;i <= len_b;++i)
  {
    while(q && a[q + 1] != b[i])
      q = prefix[q];
    if(a[q + 1] == b[i])
      ++q;
    
    if(q == len_a)
    {
      q = prefix[q];
      ++number;
      if(number <= 1000)
        result.push_back(i - len_a);
    }
  } 
  g<<number<<'\n';
  for(vector<int>::iterator it = result.begin();it != result.end();++it)
    g<<*it<<" "; 
}

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