文字列/Morris–Pratt algorithm（最小周期）
(test/string/morris-pratt.2.test.cpp)

• View this file on GitHub
• Last update: 2023-02-27 16:52:23+09:00
• Problem: https://codeforces.com/problemset/problem/1138/D

Depends on

• Morris–Pratt algorithm (include/emthrm/string/morris-pratt.hpp)

Code

/*
 * @title 文字列/Morris–Pratt algorithm（最小周期）
 *
 * verification-helper: IGNORE
 * verification-helper: PROBLEM https://codeforces.com/problemset/problem/1138/D
 */

#include <algorithm>
#include <cassert>
#include <iostream>
#include <string>

#include "emthrm/string/morris-pratt.hpp"

int main() {
  constexpr int SIGMA = 2;
  std::string s, t;
  std::cin >> s >> t;
  int num[2];
  for (int c = 0; c < SIGMA; ++c) {
    num[c] = std::count(s.begin(), s.end(), '0' + c);
  }
  const emthrm::MorrisPratt morris_pratt(t);
  std::string ans = "";
  const int period = morris_pratt.period(t.length());
  for (int pos = 0; num[t[pos] - '0'] > 0; pos = (pos + 1) % period) {
    ans += t[pos];
    --num[t[pos] - '0'];
  }
  for (int c = 0; c < SIGMA; ++c) {
    ans += std::string(num[c], '0' + c);
  }
  std::cout << ans << '\n';
  return 0;
}

#line 1 "test/string/morris-pratt.2.test.cpp"
/*
 * @title 文字列/Morris–Pratt algorithm（最小周期）
 *
 * verification-helper: IGNORE
 * verification-helper: PROBLEM https://codeforces.com/problemset/problem/1138/D
 */

#include <algorithm>
#include <cassert>
#include <iostream>
#include <string>

#line 1 "include/emthrm/string/morris-pratt.hpp"



#line 5 "include/emthrm/string/morris-pratt.hpp"
#include <vector>

namespace emthrm {

struct MorrisPratt {
  std::string s;
  std::vector<int> border;

  explicit MorrisPratt(const std::string& s) : s(s), border({-1}), j(-1) {
    const int n = s.length();
    for (int i = 0; i < n; ++i) {
      solve(i);
    }
  }

  void add(const char c) {
    s += c;
    solve(s.length() - 1);
  }

  std::vector<int> match(const std::string& t) const {
    const int n = s.length(), m = t.length();
    std::vector<int> res;
    for (int i = 0, k = 0; i < m; ++i) {
      while (k >= 0 && t[i] != s[k]) k = border[k];
      if (++k == n) res.emplace_back(i - n + 1);
    }
    return res;
  }

  int period(const int idx) const { return idx - border[idx]; }

 private:
  int j;

  void solve(const int idx) {
    while (j >= 0 && s[idx] != s[j]) j = border[j];
    border.emplace_back(++j);
  }
};

}  // namespace emthrm


#line 14 "test/string/morris-pratt.2.test.cpp"

int main() {
  constexpr int SIGMA = 2;
  std::string s, t;
  std::cin >> s >> t;
  int num[2];
  for (int c = 0; c < SIGMA; ++c) {
    num[c] = std::count(s.begin(), s.end(), '0' + c);
  }
  const emthrm::MorrisPratt morris_pratt(t);
  std::string ans = "";
  const int period = morris_pratt.period(t.length());
  for (int pos = 0; num[t[pos] - '0'] > 0; pos = (pos + 1) % period) {
    ans += t[pos];
    --num[t[pos] - '0'];
  }
  for (int c = 0; c < SIGMA; ++c) {
    ans += std::string(num[c], '0' + c);
  }
  std::cout << ans << '\n';
  return 0;
}

Back to top page