C - XX to XXX Editorial by leaf1415
与えられた文字列を、同じ文字が連続した(極大な)区間に分解し、それぞれの区間を「何の文字が何個からなる区間か」という情報で表現することを考えます。
例えば、文字列 aaabbbbaccc
は、a
が \(3\) 個からなる区間、b
が \(4\) 個からなる区間、a
が \(1\) 個からなる区間、c
が \(3\) 個からなる区間と分解できます。これを
aaabbbbaccc
= \((\) a
\(, 3)(\) b
\(, 4)(\) a
\(, 1)(\) c
\(, 3)\) と表すことにします。
一般に文字列 \(X\) を、非負整数 \(n\) 、文字 \(c_1, c_2, \ldots, c_n\) 、および正の整数 \(l_1, l_2, \ldots, l_n\) によって
\[X = (c_1, l_1)(c_2, l_2)\ldots (c_n, l_n)\]
(ただし、すべての \(i = 1, 2, \ldots, n-1\) で \(c_i \neq c_{i+1}\) )と表すことができます。 このように文字列を「何の文字が何個からなる区間か」という情報の列で表現する操作はランレングス圧縮や連長圧縮と呼ばれます。
入力で与えられた文字列 \(S, T\) がそれぞれ
\[S = (c_1, l_1)(c_2, l_2)\ldots (c_n, l_n) \tag{1}\]
\[T = (c'_1, l'_1)(c'_2, l'_2)\ldots (c'_{n'}, l'_{n'}) \tag{2}\]
と表されているとします。 問題文中の操作を \(1\) 回行うと、\(S\) において同じ文字が \(2\) 文字以上続いているある区間に、その文字がもう \(1\) つ挿入されます。 よって、問題文中の操作は「 \(1\) 以上 \(n\) 以下の整数 \(i\) で \(l_i \geq 2\) を満たすものを一つ選んで \(l_i\) の値を \(1\) 増加させる操作」とみなすことができます。 この操作を繰り返して \(S\) を \(T\) に一致させることができる必要十分条件は、下記の \(3\) つの条件をすべて満たすことです。
- \(n = n'\)
- すべての \(i = 1, 2, \ldots, n\) について、\(c_i = c'_i\)
- すべての \(i = 1, 2, \ldots, n\) について、次のどちらかが成り立つ
- \(l_i = l'_i\)
- \(l_i \lt l'_i\) かつ \(l_i \geq 2\)
よって、本問題を解くには、
- まず、\(S\) と \(T\) をランレングス圧縮して (1) と (2) の表現を得た後、
- それが上記の条件 1. から条件 3. をすべて満たすかどうかを判定すれば良いです。
どちらも \(\mathrm{O}(|S|+|T|)\) 時間で行うことができるので、 本問題を \(\mathrm{O}(|S|+|T|)\) 時間で解くことができます。
C++ 言語による本問題の正解例を以下に記載します。
#include <iostream>
#include <vector>
#include <utility>
using namespace std;
void rle(string s, vector<pair<char, int>> &vec)
{
int cnt = 1;
for(int i = 1; i < (int)s.size(); i++){
if(s[i] != s[i-1]){
vec.push_back({s[i-1], cnt});
cnt = 0;
}
cnt++;
}
vec.push_back({s.back(), cnt});
}
int main(void)
{
string s, t;
cin >> s >> t;
vector<pair<char, int>> svec, tvec;
rle(s, svec), rle(t, tvec);
if(svec.size() != tvec.size()){
cout << "No" << endl;
return 0;
}
bool ans = true;
for(int i = 0; i < svec.size(); i++){
if(svec[i].first != tvec[i].first) ans = false;
if(!(svec[i].second == tvec[i].second || svec[i].second < tvec[i].second && svec[i].second >= 2)) ans = false;
}
if(ans) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}
posted:
last update: