View on GitHub

cp-library

永続文字列

C++ 用ライブラリ一覧に戻る

ソースコード

nachia/string/persistent-string.hpp

主な機能

文字列(バイト列)の連結、分割を非破壊的に行う。コピーペーストの繰り返しによって通常よりも長い文字列を生成でき、長さ $2^{60}$ まで表現できる。

$1$ バイトずつ二分探索木の葉に乗せるのに比べて、メモリ使用量を抑えるようにしている。

struct nachia::PersistentString

コンストラクタ

PersistentString(const std::string& s = "");
PersistentString(const char* s);

文字列を与えて初期化する。

また、コピーとムーブが可能である。

std::string と共通の部分

MyType substr(size_t pos, size_t len) const; // (1)
bool empty() const noexcept; // (2)
size_t size() const noexcept; // (2)

メインの機能は std::string のものと同様である。

operator+ , +=

MyType operator+(MyType rh) const;
MyType& operator+=(MyType rh);

std::string の演算と同じである。

operator* , *=

MyType operator*(size_t z) const;
MyType& operator*=(size_t z);

文字列を $z$ 回繰り返した文字列を取得する。

$z=0$ ならば空文字列を取得する。

insert, inserted

void insert(MyType other, size_t pos);
MyType inserted(MyType other, size_t pos) const;

位置 begin+pos に他の文字列を挿入する。 inserted は this の内容を破壊しない。

to_string

std::string to_string();

文字列を明示的に取得する。

使用例

JOI2011/2022 春季トレーニング合宿 : copypaste - コピー&ペースト (https://atcoder.jp/contests/joisc2012/tasks/joisc2012_copypaste)

#include <iostream>
#include <nachia/string/persistent-string.hpp>

int main(){
    int M; std::cin >> M;
    std::string buf; std::cin >> buf;
    auto S = nachia::PersistentString(buf);
    int Q; std::cin >> Q;
    for(int i=0; i<Q; i++){
        unsigned int l,r,p; std::cin >> l >> r >> p;
        S = S.inserted(S.substr(l, r-l), p).substr(0, M);
    }
    std::cout << S.to_string() << '\n';
    return 0;
}

参考


TOP PAGE