Next Element Index (次の各要素の登場位置)
(string/next_element_index.hpp)

• View this file on GitHub
• Last update: 2024-12-04 12:30:48+09:00
• Include: #include "string/next_element_index.hpp"

使い方

std::string s;
auto res = next_element_index(s);

res[i][c] は $i = 0, 1, … , n$ について, $s[i, n)$ において次の c の登場位置を返す

c は与えられた配列の要素の最小値を基準としたときの差分である (a - z なら a が $0$, b が $1$, … , z が $26$ となる)

参考文献

Code

#pragma once

#include <limits>
#include <string>
#include <vector>

// nextelement index
// res[i][c] = s[i, n) において次の c の登場位置を返す
template <class T> std::vector<std::vector<int>> next_element_index(const std::vector<T>& s) {
    const int n = (int)(s.size());
    T lb = std::numeric_limits<T>::max(), ub = std::numeric_limits<T>::min();
    for (int i = 0; i < n; i++) {
        if (lb > s[i]) lb = s[i];
        if (ub < s[i]) ub = s[i];
    }
    const int sigma = ub - lb + 1;
    std::vector res(n + 1, std::vector<int>(sigma, -1));
    for (int i = n - 1; i >= 0; i--) {
        res[i] = res[i + 1];
        res[i][s[i] - lb] = i;
    }
    return res;
}

std::vector<std::vector<int>> next_element_index(const std::string& s) {
    const int n = (int)(s.size());
    std::vector<int> s2(n);
    for (int i = 0; i < n; i++) s2[i] = s[i];
    return next_element_index(s2);
}

#line 2 "string/next_element_index.hpp"

#include <limits>
#include <string>
#include <vector>

// nextelement index
// res[i][c] = s[i, n) において次の c の登場位置を返す
template <class T> std::vector<std::vector<int>> next_element_index(const std::vector<T>& s) {
    const int n = (int)(s.size());
    T lb = std::numeric_limits<T>::max(), ub = std::numeric_limits<T>::min();
    for (int i = 0; i < n; i++) {
        if (lb > s[i]) lb = s[i];
        if (ub < s[i]) ub = s[i];
    }
    const int sigma = ub - lb + 1;
    std::vector res(n + 1, std::vector<int>(sigma, -1));
    for (int i = n - 1; i >= 0; i--) {
        res[i] = res[i + 1];
        res[i][s[i] - lb] = i;
    }
    return res;
}

std::vector<std::vector<int>> next_element_index(const std::string& s) {
    const int n = (int)(s.size());
    std::vector<int> s2(n);
    for (int i = 0; i < n; i++) s2[i] = s[i];
    return next_element_index(s2);
}

Back to top page