プログラミングのお題スレ Part22

プログラミングのお題スレ Part22 at TECH

1:デフォルトの名無しさん
23/08/03 13:52:13.20 /xW45k0z.net
プログラミングのお題スレです。
【出題と回答例】
1 名前：デフォルトの名無しさん
　お題：お題本文
2 名前：デフォルトの名無しさん
　 >>1 使用言語
　回答本文
　結果がある場合はそれも
【ソースコードが長くなったら】 (オンラインでコードを実行できる)
URLﾘﾝｸ(ideone.com)
URLﾘﾝｸ(codepad.org)
URLﾘﾝｸ(compileonline.com)
URLﾘﾝｸ(rextester.com)
URLﾘﾝｸ(runnable.com)
URLﾘﾝｸ(code.hackerearth.com)
URLﾘﾝｸ(melpon.org)
URLﾘﾝｸ(paiza.io)
宿題は宿題スレがあるのでそちらへ。
※前スレ
プログラミングのお題スレ Part21
ｽﾚﾘﾝｸ(tech板)

82:デフォルトの名無しさん
23/08/27 00:17:21.22 3rRjeZjU.net
>>79
動いている様子を確認させていただきました！！ありがとうございました！

当チケットはこれにてクローズとさせていただきたいと思いますヽ(=´▽`=)ﾉ

83:デフォルトの名無しさん
23/08/27 01:14:16.06 xDzSjAxc.net
>>78
こうすると計算量を減少できる

fn len_of_eq(s: &str, index: usize, even: usize) -> usize {
　let mut len = 0;
　for (p, q) in std::iter::zip(s[(index + even)..].chars(), s[0..=index].chars().rev()) {
　　if p != q {
　　　break;
　　}
　　len += 1;
　}
　return len;
}

fn print_kaibun(s: &str) {
　for index in 0..s.len() {
　　for even in 0..=1 {
　　　for len in 1..=len_of_eq(s, index, even) {
　　　　let first = index + 1 - len;
　　　　let last = index + len - 1 + even;
　　　　println!("{first}～{last}: {}", &s[first..=last]);
　　　}
　　}
　}
}

fn main() {
　print_kaibun("ABCBAXYZZYX");
}

84:デフォルトの名無しさん
23/08/27 01:16:42.56 xDzSjAxc.net
まずこの部分が最初のヒントで

＞＞それって例えば "ABCBAXYZZYX" だったら "ABCBA" と "XYZZYX" が抜き出せれば良いの?
＞＞途中の "BCB", "C", "YZZY", "ZZ" も抜き出すの?
＞途中のもぜんぶっす…

最も長いものを抜き出せばその一部分はその中に含まれている
だから短いのが判明した時点で引き続き長いのも探索しないと多重に無駄に比較が行なわれてしまう

もう一つのポイントは回文は対称系で長さ奇数と偶数の二種類があること
長さ奇数「DCBABCD」と長さ偶数「DCBAABCD」どちらの場合も
比較は対称点となるAからのみ出発して比較していけばよくて
順方向＆逆方向へ最長分を比較していけば上述の無駄な比較を減らせる

このような順番で見つかっていくことになる
>>83の実行結果
0～0: A
1～1: B
2～2: C
1～3: BCB
0～4: ABCBA
3～3: B
4～4: A
5～5: X
6～6: Y
7～7: Z
7～8: ZZ
6～9: YZZY
5～10: XYZZYX
8～8: Z
9～9: Y
10～10: X

2から表示