calc-next
(lib/string/calc_next.hpp)

• View this file on GitHub
• Last update: 2024-05-04 18:06:16+09:00
• Include: #include "lib/string/calc_next.hpp"

calc-next

概要

文字列 $S$ において、ある地点からある文字が次にどの地点に出てくるかを計算します。

calc-prev については、文字列 $S$ において、ある文字がある地点以前のどの地点に出てくるかを計算します。

計算量

$\mathrm{O}(\lvert S\lvert)$

Code

#pragma once

/**
 * @brief calc-next
 * @docs docs/string/calc_next.md
 */

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

    vector<vector<int>> res(n + 1, vector<int>(26, n));

    for(int i = n - 1; i >= 0; i--){
        res[i] = res[i + 1];
        res[i][s[i] - 'a'] = i;
    }
    return res;
}

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

    vector<vector<int>> res(n + 1, vector<int>(26, -1));

    for(int i = 0; i < n; i++){
        if(i >= 1) res[i] = res[i - 1];
        res[i][s[i] - 'a'] = i;
    }
    return res;
}

#line 2 "lib/string/calc_next.hpp"

/**
 * @brief calc-next
 * @docs docs/string/calc_next.md
 */

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

    vector<vector<int>> res(n + 1, vector<int>(26, n));

    for(int i = n - 1; i >= 0; i--){
        res[i] = res[i + 1];
        res[i][s[i] - 'a'] = i;
    }
    return res;
}

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

    vector<vector<int>> res(n + 1, vector<int>(26, -1));

    for(int i = 0; i < n; i++){
        if(i >= 1) res[i] = res[i - 1];
        res[i][s[i] - 'a'] = i;
    }
    return res;
}

Back to top page