プログラミングのお題スレ Part22 (857ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
81(1): デフォルトの名無しさん [sage] 2023/08/27(日) 01:14:16.06 ID:xDzSjAxc(1/2) AAS
>>7676(2): 蟻人間 ◆T6xkBnTXz7B0 [sage] 2023/08/26(土) 23:29:51.32 ID:JYg5slq9(2/3) AAS
>>71 C++
#include <stdio.h>
bool is_kaibun(const char *str, size_t len)
{
for (size_t i = 0; i < len/2; i++)
if (str[i] != str[len - i - 1]) return false;
return true;
}
void detect_kaibun(const char *str, size_t len)
{
for (size_t klen = 1; klen <= len; klen++)
{
for (size_t i = 0; i < len - klen + 1; i++)
if (is_kaibun(str + i, klen))
printf("%*s\n", (int)klen, str + i);
}
}
int main(void)
{
detect_kaibun("ABCBCXC", 7);
return 0;
}
こうすると計算量を減少できる
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");
}
82: デフォルトの名無しさん [sage] 2023/08/27(日) 01:16:42.56 ID:xDzSjAxc(2/2) AAS
まずこの部分が最初のヒントで
＞＞それって例えば "ABCBAXYZZYX" だったら "ABCBA" と "XYZZYX" が抜き出せれば良いの?
＞＞途中の "BCB", "C", "YZZY", "ZZ" も抜き出すの?
＞途中のもぜんぶっす…
最も長いものを抜き出せばその一部分はその中に含まれている
だから短いのが判明した時点で引き続き長いのも探索しないと多重に無駄に比較が行なわれてしまう
もう一つのポイントは回文は対称系で長さ奇数と偶数の二種類があること
長さ奇数「DCBABCD」と長さ偶数「DCBAABCD」どちらの場合も
比較は対称点となるAからのみ出発して比較していけばよくて
順方向＆逆方向へ最長分を比較していけば上述の無駄な比較を減らせる
このような順番で見つかっていくことになる
>>81の実行結果
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
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.045s