用途
文字列のith以降で文字cが出現する最小のindexを返す. 存在しなければ文字列長を返す.
計算量
$ O(n) $
使い方
1
| auto res = nextCharIndex(s);
|
sはstd::string, res[i][j]でith以降(ithも含む)で文字cが出現するindexを得る.
実装
1
2
3
4
5
6
7
8
9
10
11
12
| vector<vector<int>> nextCharIndex(string &_s) {
vector m(_s.size() + 1, vector<int>(26));
for (int i = 0; i < 26; i++)
m[_s.size()][i] = _s.size();
for (int i = _s.size() - 1; i >= 0; i--)
for (int j = 0; j < 26; j++)
if (_s[i] - 'a' == j)
m[i][j] = i;
else
m[i][j] = m[i + 1][j];
return m;
}
|
Verify👍
https://atcoder.jp/contests/typical90/submissions/57632650