Cod sursa(job #3161490)

Utilizator dnprxDan Pracsiu dnprx Data 27 octombrie 2023 11:53:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>
using namespace std;
/// Z-Algorithm

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string str, pat;

vector<int> Z()
{
  int n = str.size();
  int l = 0, r = 0;
  vector<int> z(n, 0);
  for (int i = 1; i < n; ++i)
  {
        if (i < r)
            z[i] = min(r - i, z[i - l]);
        while (i + z[i] < n && str[z[i]] == str[i + z[i]])
            z[i]++;
        if (i + z[i] > r)
        {
            r = i + z[i];
            l = i;
        }
  }
  return z;
}

int main()
{
  fin >> pat >> str;
  str = pat + "$" + str;
  vector<int> z = Z();

  vector<int> ans;
  int cnt = 0;
  for (int i = pat.size() + 1; i < str.size(); i++)
    if (z[i] == pat.size())
    {
      cnt++;
      if ((int)ans.size() < 1000)
        ans.emplace_back(i - pat.size() - 1);
    }
  fout << cnt << '\n';
  for (int i : ans)
    fout << i << ' ';
}