木の中心が直径上に存在すること 中心を見つけるアルゴリズム について書きます。 木の中心とは「各頂点への距離の最大値」が最小になる頂点 (の集合) です。 頂点 $v$ から各頂点への距離の最大値を $ E(v) $ と書きます。つまり、 $$ E(v) = \max_u\{\math…

テキスト文字列 txt にパターン文字列 pat が現れる位置を求めます。 たとえば txt = "abaaaba", pat = "aab" のとき、テキストの $4$ 文字目からパターンが現れます。 abaaaba aab 素朴な方法として、パターンの開始位置を全通り試すというものがあります。…