Cod sursa(job #3269176)

Utilizator ArseniuVictorStefanArseniu Victor Stefan ArseniuVictorStefan Data 18 ianuarie 2025 12:43:23
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.05 kb
#include <bits/stdc++.h>

#define LMAX 2000000

using namespace std;

struct alphabet_t {
  int remap[256];
  int size;

  void add(char c) {
    remap[c] = size++;
  }
};

vector<int> prefix_function(const string& s)
{
  int n = s.size();
  vector<int> pi(n);

  pi[0] = 0;
  for (int i = 1; i < n; i++) {
    int j = pi[i - 1];
    while (j > 0 && s[j] != s[i]) {
      j = pi[j - 1];
    }

    if (s[j] == s[i]) {
      j++;
    }

    pi[i] = j;
  }

  return pi;
}

struct pairhash {
  size_t operator()(const pair<int, int>& p) const
  {
    return hash<int>()(p.first + p.second * LMAX);
  }
};

unordered_map<pair<int, int>, int, pairhash> build_automaton(const string& s, const alphabet_t& alphabet)
{
  int n = s.size();
  unordered_map<pair<int, int>, int, pairhash> aut;

  vector<int> pi = prefix_function(s);
  for (int i = 0; i <= n; i++) {
    for (int c = 0; c < alphabet.size; c++) {
      if (i < n && c == alphabet.remap[s[i]]) {
        aut.emplace(pair<int, int>{ i, c }, i + 1);
      } else if (i != 0) {
        auto it = aut.find(pair<int, int>{ pi[i - 1], c });
        if (it != aut.end()) {
          aut.emplace(pair<int, int>{ i, c }, it->second);
        }
      }
    }
  }
  return aut;
}

int main()
{
  alphabet_t alphabet;
  alphabet.size = 0;

  for (char c = '0'; c <= '9'; c++) {
    alphabet.add(c);
  }

  for (char c = 'a'; c <= 'z'; c++) {
    alphabet.add(c);
  }

  for (char c = 'A'; c <= 'Z'; c++) {
    alphabet.add(c);
  }

  ifstream cin("strmatch.in");
  ofstream cout("strmatch.out");

  string s, t;
  cin >> s >> t;

  auto aut = build_automaton(s, alphabet);

  int cnt = 0;
  vector<int> ans;

  int q = 0;
  for (int i = 0; i < t.size(); i++) {
    auto it = aut.find(pair<int, int>{ q, alphabet.remap[t[i]] });
    if (it != aut.end()) {
      q = it->second;
    } else {
      q = 0;
    }

    if (q == s.size()) {
      if (cnt < 1000) {
        ans.push_back(i - s.size() + 1);
      }

      cnt++;
    }
  }

  cout << cnt << "\n";
  for (int i = 0; i < ans.size(); i++) {
    cout << ans[i] << " ";
  }
  cout << "\n";

  return 0;
}