Seimei Handan 999.0 (JAG 2022年模擬地区予選F) を決定的に解く
この記事は帰ってきた AOJ-ICPC Advent Calendar 2022 - Adventarの20日目の記事です．
問題概要
各要素が $1$ 以上 $L$ 以下の整数列 $A = (a_1,\dots,a_N),B = (b_1,\dots,b_M)$ が与えられる．
整数に対して定義される全単射の写像 $f : [1,L] \rightarrow [1,L]$ の内，$(f(a_1),\dots,f(a_n))$ の部分連続列として $B = (b_1,\dots,b_M)$ を含むようなものは何通りあるか，modulo 998,244,353 で答えよ．
制約
- $1\leq N \leq 300,000$
- $1 \leq M \leq N$
- $1 \leq L \leq 300,000$
（以下のリンク先に正式な問題文があります）
2022/Practice/模擬地区予選/問題文とデータセット - ICPC OB/OG の会
はじめに（ここからネタバレあり）
この問題は，ハッシュを利用して解くこともできます（解説の想定解 1 ）．
以下では，個人的興味から文字列アルゴリズムを駆使して決定的に解く方法を書きます（つまり，解説の想定解 2 について詳しく書きます）．
問題の言い換え
$i$ 番目の index から始まる連続部分列$(f(a_{i}),\dots , f( a_{ i + M - 1 } ))$ が $B$ に一致することを考えます．このとき，そのような $f$ が存在する場合，$(a_{i},\dots , a_{ i + M - 1 } )$ に含まれる数字の変換先は一意に特定され，それ以外の数字に関してはどのような割り当ても許されることになります．よって，$(f(a_{i}),\dots , f( a_{ i + M - 1 } ))$ が $B$ に一致する $f$ が存在するならば，$(a_{i},\dots,a_{ i + M - 1 })$ に含まれる数字の種類を$L'$ として $(L-L')!$ 通りの $f$ が条件を満たします．
異なる $i, j$ について，$(a_{i},\dots,a_{ i + M - 1 })$ と $(a_{j},\dots,a_{ j + M - 1 })$ がそれぞれ条件を満たす$f$ を持つ場合を考えます．このとき，条件を満たす$f$ の集合は、$(a_{i},\dots,a_{ i + M - 1 }) = (a_{j},\dots,a_{ j + M - 1 })$ ならば、明らかに両者で一致します．逆に $(a_{i},\dots,a_{ i + M - 1 }) \neq (a_{j},\dots,a_{ j + M - 1 })$ ならば，disjoint であることが分かります．これらは$A$の部分連続列同士が一致するかの判定なので，suffix array, LCP array を用いれば決定的な判定が可能です．*1
以上より，「$(f(a_{i}),\dots , f( a_{ i + M - 1 } ))$ が $B$ に一致する $f$ が存在する」ような $i$ を全て求めた後に，部分列 $(a_{i},\dots , a_{ i + M - 1 } )$ の種類が何種類あるかを求められれば $f$ の総数が分かります．部分列 $(a_{i},\dots , a_{ i + M - 1 } )$ の種類が何種類あるかは、$A$の部分連続列同士が一致判定と同様に，suffix array, LCP array を用いて計算できます．こちらに関しては suffix array, LCP array を使う例題としてよく出てくるものなので、割愛させていただきます．
背景知識：parameterized pattern matching
上記の議論から、「$(f(a_{i}),\dots , f( a_{ i + M - 1 } ))$ が $B$ に一致する $f$ が存在する」ような $i$ が全て求められればよいことが分かりました．
この条件には，parameterized pattern matching [1] という概念が背景知識としてあります．ざっくりとした定義は以下の通りです．
定義: (parameterized pattern matching)
parameterized string (p-string) は constant と parameter の大きく分けて2種類の（広義の）文字からなる
- constant: いわゆる通常の文字に対応する． *2
- parameter: 変数に対応する（後述する p-match を参照）．
2つの p-string $S, T$ が parameterized match (p-match) するとは以下の状況を指す．
- parameter の（有限）集合を $\Pi$ として、ある $\Pi \rightarrow \Pi$ となる全単射$f$ が存在し，$S$ に含まれる parameters を $f$ で変換したときに $T$ と一致する．
例: p-match
constants: $\text{A},\text{B},\text{C}$, parameters: {$x,y,z$} とするとき，以下のようになります．
- $\text{A}x\text{B}yx$ と $\text{A}z\text{B}yz$ は p-match する ($f(x)=z, f(y)=y,f(z)=x$)
- $\text{A}x\text{B}yx$ と $\text{A}z\text{B}zz$ は p-match しない ($f(x)= f(y)=z$ は許されない)
- $\text{A}x\text{B}yx$ と $\text{A}z\text{C}yz$ は p-match しない (3文字目が $\text{B} \neq \text{C}$)
parameterized pattern matching という概念を用いると、今回の問題は「parameters のみからなる p-string $A,B$に対して、$B$ に p-match する $A$ の連続部分列 (p-substring) を全て求めよ」という問題になります．
prev encoding
p-string に対して、以下の変換 prev encoding を考えます（今回の問題では parameters のみを考えればよいですが，一応 constants も考えることにします）．
定義: (prev encoding)
p-string $S$に対して、$S$ と同じ長さの列 $\text{prev}(S)$を以下のように定義する．
- $i$番目の文字 $x$ が constant の場合: $\text{prev}(S)[i] = x$
- $i$番目の文字 $x$ が parameter の場合:
- $x$ が p-string 内で先頭から見て初めて現れた場合: $\text{prev}(S)[i] = 0$
- そうでない場合: $\text{prev}(S)[i] = i - (i$番目より前で直近に出現した$x$の位置)
例えば， p-string $\text{A}x\text{B}yxy$ に対して，$\text{prev}(\text{A}x\text{B}yxy) = \text{A}0\text{B}032$ となります．
この時，prev encoding は以下の重要な性質を満たします．
性質: p-string $S, T$ が p-match $\Leftrightarrow$ $\text{prev}(S) = \text{prev}(T)$
よって，p-string の p-match が prev encoding した文字列の一致として判定可能になります．
Morris-Pratt algorithm を p-string に適用する
文字列検索の有名なアルゴリズムとして Morris-Pratt algorithm (以下，MP 法) があります．
MP 法は長さ $n$ の文字列 $S$ が与えられた際に，$0\leq i < n$ について $S[0:i]$ の接頭辞と接尾辞が最大何文字一致しているか(ただし，$S[0:i]$ そのものは除く)の配列を計算するアルゴリズムです．この配列を用いて、文字列検索を行うことができます（MP法の詳細の説明は割愛します．例えば，文字列の頭良い感じの線形アルゴリズムたち - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ や https://hcpc-hokudai.github.io/archive/string_algorithms_001.pdf などで説明されています）．
実は通常の文字列に対する MP 法にほんの少しの修正を加えるだけで，p-string に対する文字列検索を行うことができます．以下では，問題の設定と同様に parameter のみからなる p-string について扱います（constant なものが混じっている場合でもほとんど同じようなコードでできます）．
通常の MP 法 (入力の文字列 $s$, 求める配列は table に格納される)
class MP
{
public:
string pattern;
int plen;
vector<int> table;
MP(const string& s) : pattern(s), plen((int)pattern.size()), table(plen + 1){
table[0] = -1;
int j = -1;
for(int i = 0; i < plen; ++i){
while(j >= 0 && pattern[i] != pattern[j]){
j = table[j];
}
table[i+1] = ++j;
}
}
void search(const string& text, vector<int>& res){
int head = 0, j = 0, tlen = (int)text.size();
while(head + j < tlen){
if(pattern[j] == text[head + j]) {
if(++j == plen){
res.push_back(head);
head = head + j - table[j];
j = table[j];
}
}else{
head = head + j - table[j];
if(j) j = table[j];
}
}
}
};
p-string の MP 法 (ただし，入力 $s$ は p-string を prev encoding したもの)
class MP
{
public:
vector<int> pattern;
int plen;
vector<int>table;
MP(const vector<int>& s):pattern(s),plen((int)pattern.size()),table(plen+1){
table[0] = -1;
int j = -1;
for(int i=0;i<plen;i++){
while(j>=0 && pattern[j] != (pattern[i]<=j ? pattern[i] : 0)){
j = table[j];
}
table[i+1] = ++j;
}
}
void search(const vector<int>& text,vector<int> &res){
int head = 0, j = 0,tlen = (int)text.size();
while(head + j < tlen){
if(pattern[j] == (text[head+j]<=j ? text[head+j] : 0)){
if(++j == plen){
res.push_back(head);
head = head + j - table[j];
j = table[j];
}
}else{
head = head + j - table[j];
if(j) j = table[j];
}
}
}
};コードを見比べてもらえれば分かりますが，文字の不一致判定を
pattern[j] != (hoge[*]<=j ? hoge[*] : 0)
に修正しているだけです．
逆になぜ文字列の比較に修正が必要かというと，prev encoding した文字列について部分文字列の比較を考える際に，
$S[i:i+x]$ と $S[j,j+x]$ が p-match する $\not\Leftrightarrow$ $\text{prev}(S)[i:i+x] = \text{prev}(S)[j:j+x]$
であるためです．
例えば，$S = xyzzxy$ について，$\text{prev}(S) = 000144$ となり，$\text{prev}(S)[0:3] = 000 \neq 144 = \text{prev}(S)[3:6]$ ですが，$S[0:3] = xyz$ と $S[3:6] = zxy$ は p-match します．
そこで，prev encoding を見て部分文字列の一致を判定する際には，各文字の prev について参照している index が現在の部分文字列の先頭より前かどうかを確認した上で判定してやればよいです．これが MP 法を修正した箇所となります．
逆に，文字の一致判定以外は，通常の文字列に対する MP 法の正当性の議論と同様の議論をすることで、p-string に対する MP 法も問題なく動くことが分かります．
全実装
以上より，この問題は解くことができます．実装例は以下の通りです（suffix array と LCP array でやるところはサボって Rolling Hash で書きました）
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
typedef long long ll;
class MP
{
public:
vector<int> pattern;
int plen;
vector<int>table;
MP(const vector<int>& s):pattern(s),plen((int)pattern.size()),table(plen+1){
table[0] = -1;
int j = -1;
for(int i=0;i<plen;i++){
while(j>=0 && pattern[j] != (pattern[i]<=j ? pattern[i] : 0)){
j = table[j];
}
table[i+1] = ++j;
}
}
void search(const vector<int>& text,vector<int> &res){
int head = 0, j = 0,tlen = (int)text.size();
while(head + j < tlen){
if(pattern[j] == (text[head+j]<=j ? text[head+j] : 0)){
if(++j == plen){
res.push_back(head);
head = head + j - table[j];
j = table[j];
}
}else{
head = head + j - table[j];
if(j) j = table[j];
}
}
}
};
struct RH{
static int mod[2], mul[2];
static vector<int> pm[2];
int sz;
vector<vector<int> > hs;
RH(const vector<int>& s): sz((int)s.size()),hs(2,vector<int>(sz+1,0)){
rep(i,2){
if(pm[i].empty())pm[i].push_back(1);
rep(j,sz){
hs[i][j+1] = ((ll)hs[i][j] * mul[i] + s[j])% mod[i];
}
}
}
pair<int,int> hash(int l,int r){
if(l>=r)return {0,0};
int res[2];
rep(i,2){
while(pm[i].size() <= r){
pm[i].push_back((ll)pm[i].back() * mul[i] % mod[i]);
}
res[i] = (hs[i][r] - (ll)hs[i][l] * pm[i][r-l])%mod[i] + mod[i];
res[i] = (res[i] >= mod[i]) ? (res[i]-mod[i]) : res[i];
}
return {res[0],res[1]};
}
};
vector<int> RH::pm[2];
int RH::mod[2] = {1000000007,1000000009}, RH::mul[2] = {10009,10007};
ll MOD = 998244353;
ll fac[300001];
vector<int> prev_encoding(vector<int>&a){
map<int,int> last_id;
int n = a.size();
vector<int> prev(n);
rep(i,n){
if(last_id.find(a[i])==last_id.end()){
prev[i] = 0;
}else{
prev[i] = i - last_id[a[i]];
}
last_id[a[i]] = i;
}
return prev;
}
int main(){
fac[0] = 1;
for(int i=1;i<=300000;i++){
fac[i] = fac[i-1] * i % MOD;
}
int n,m,L;
cin >> n >> m >> L;
vector<int> a(n);
vector<int> b(m);
rep(i,n) cin >> a[i];
rep(i,m) cin >> b[i];
vector<int> A = prev_encoding(a);
vector<int> B = prev_encoding(b);
int C = 0;
rep(i,m)C += (B[i]==0);
MP mp(B);
vector<int> res;
mp.search(A,res);
set<pair<int,int> > st;
RH rh(a);
for(auto x:res){
st.insert(rh.hash(x,x+m));
}
cout << fac[L-C] * st.size() % MOD << endl;
return 0;
}
参考文献
1. B. S. Baker, "A Theory of Parameterized Pattern Matching: Algorithms and Applications," In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, pp. 71--80, 1993.
感想
実は，私の修士時代の最初の研究テーマが parameterized pattern matching に関連する内容でした．Twitter で何度か parameterized pattern matching 出すか～(笑) みたいなことを言っていたので，そのものが出てきてコンテスト中本当にビックリしました．
今回の問題では p-string の prev encoding さえ分かれば解ける問題となっていましたが，この記事では Morris-Pratt algorithm を修正して適用したように，p-string に対して普通の文字列と同様に様々な計算ができることが知られています（例えば，pSA, pLCP, pST, pBWT ... などいろいろとできます．簡潔データ構造も提案されています）．最近でも論文が出ている認識なので，興味のある方は深堀りしてみると面白いと思います．*3
