The longest constant gene (UVa Live Archive)
問題
遺伝子がn個あり、それぞれの長さはliである。共通部分の長さの最大値を答えよ。
li<1000000
1
解法
間に0,1,2,...と挟んで各文字列を連結する。その後Suffix Arrayとlcpを求めて最長の部分を見つければ良い。文字列が長すぎてO(n)のSuffix Arrayじゃないと無理っぽいのでSA-IS*1を使った。というかこれ勝手に使っていいんかな。
遺伝子がn個あり、それぞれの長さはliである。共通部分の長さの最大値を答えよ。
li<1000000
1
間に0,1,2,...と挟んで各文字列を連結する。その後Suffix Arrayとlcpを求めて最長の部分を見つければ良い。文字列が長すぎてO(n)のSuffix Arrayじゃないと無理っぽいのでSA-IS*1を使った。というかこれ勝手に使っていいんかな。