結果
問題 | No.599 回文かい |
ユーザー | phspls |
提出日時 | 2023-01-14 00:48:07 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 353 ms / 4,000 ms |
コード長 | 1,409 bytes |
コンパイル時間 | 2,363 ms |
コンパイル使用メモリ | 140,552 KB |
実行使用メモリ | 198,160 KB |
最終ジャッジ日時 | 2023-08-26 05:49:31 |
合計ジャッジ時間 | 3,756 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 1 ms
4,380 KB |
testcase_04 | AC | 1 ms
4,380 KB |
testcase_05 | AC | 1 ms
4,380 KB |
testcase_06 | AC | 1 ms
4,380 KB |
testcase_07 | AC | 2 ms
4,376 KB |
testcase_08 | AC | 1 ms
4,380 KB |
testcase_09 | AC | 1 ms
4,376 KB |
testcase_10 | AC | 118 ms
94,444 KB |
testcase_11 | AC | 70 ms
56,208 KB |
testcase_12 | AC | 134 ms
106,804 KB |
testcase_13 | AC | 78 ms
62,576 KB |
testcase_14 | AC | 217 ms
159,560 KB |
testcase_15 | AC | 231 ms
183,852 KB |
testcase_16 | AC | 309 ms
173,784 KB |
testcase_17 | AC | 353 ms
198,160 KB |
testcase_18 | AC | 1 ms
4,376 KB |
testcase_19 | AC | 1 ms
4,376 KB |
testcase_20 | AC | 1 ms
4,376 KB |
evil_0.txt | AC | 176 ms
133,604 KB |
ソースコード
const MOD: usize = 1e9 as usize + 7; fn zalgorithm(s: &str) -> Vec<usize> { let n = s.len(); let svec = s.chars().collect::<Vec<_>>(); let mut ret = vec![0usize; n]; ret[0] = n; let mut i = 1usize; let mut j = 0usize; while i < n { while i+j < n && svec[j] == svec[i+j] { j += 1; } ret[i] = j; if j == 0 { i += 1; continue; } let mut k = 1usize; while k < j && k + ret[k] < j { ret[i+k] = ret[k]; k += 1; } i += k; j -= k; } ret } fn dfs(idx: usize, dists: &Vec<Vec<usize>>, memo: &mut Vec<Option<usize>>) -> usize { if idx * 2 == dists[0].len() { return 1usize; } if let Some(x) = memo[idx] { return x; } let n = dists[0].len() - 2*idx; let mut ret = 1usize; for size in 1..=n/2 { if dists[idx][n-size] == size { ret += dfs(idx+size, dists, memo); ret %= MOD; } } memo[idx] = Some(ret); ret } fn main() { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); let s = s.trim(); let mut dists = Vec::with_capacity(s.len()/2+1); let mut memo = vec![None; s.len()+1]; for i in 0..s.len()/2 { dists.push(zalgorithm(&s[i..s.len()-i])); } println!("{}", dfs(0, &dists, &mut memo)); }