プログラミングのお題スレ Part22 (854ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
76(2): 蟻人間 ◆T6xkBnTXz7B0 [sage] 2023/08/26(土) 23:29:51.32 ID:JYg5slq9(2/3) AAS
>>7171(3): デフォルトの名無しさん [sage] 2023/08/26(土) 20:03:48.42 ID:LJcWLtrE(1) AAS
文字列Sの中に含まれる回文をすべて列挙ってどうやったらいいですかね(*_*)
aとかbみたいな一文字でも回文とみなしますです
文字列Sは1文字以上100文字以下で、半角英字であることがわかってます
とんでもない計算量になる気がするのですが、鮮やかなやりかたってないものかと…トホ(ヽ´ω`)
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;
}
77(2): 蟻人間 ◆T6xkBnTXz7B0 [sage] 2023/08/26(土) 23:37:32.47 ID:JYg5slq9(3/3) AAS
>>76 間違えた。
printf("%*s\n", (int)klen, str + i);
を
printf("%.*s\n", (int)klen, str + i);
に訂正。
81(1): デフォルトの名無しさん [sage] 2023/08/27(日) 01:14:16.06 ID:xDzSjAxc(1/2) AAS
>>76
こうすると計算量を減少できる
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");
}
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 1.398s*