ZAlgorithm実装

[takytank]

ZAlgorithmの実装を追加しました。 #6

ほとんど元のC++のコードそのままとなっています。 元のコードで

int& k = z[i];
k = (j + z[j] <= i) ? 0 : std::min(j + z[j] - i, z[i - j]);
while (i + k < n && s[k] == s[i + k]) k++;
if (j + z[j] < i + z[i]) j = i;

のように参照を使用してる部分の実装に悩み、元のコードの形を保つ方針で unsafe とポインタを使用しましたが、問題ないでしょうか？ unsafeは使用しない方がよいということであれば、k の部分はそのまま z[i] に置き換えて修正しようかと思います。

動作確認は以下の提出で行いました。 https://atcoder.jp/contests/abc141/submissions/16581227

よろしくお願いします。

[terry-u16]

おお仕事が早い……！ 参照部分の移植ですが、refキーワードを使ってあげるとunsafeを使わずとも同等の動作ができるかなと思います。

ref int k = ref z[i];
k = (j + z[j] <= i) ? 0 : System.Math.Min(j + z[j] - i, z[i - j]);
while (i + k < n && s[k] == s[i + k]) (k)++;
if (j + z[j] < i + z[i]) j = i;

コードお借りしてしまいましたが、こちらでもACできることを確認しました。 https://atcoder.jp/contests/abc141/submissions/16582114

[takytank]

refで実現できること知りませんでした。 C# 7.0の機能なのですね……

ポインタを使うより間違いなく分かり易いと思うので、変更します。

[takytank]

修正完了しました。

[key-moon]

ありがとうございます…! 確認しました。