글 읽기 - 계속 틀렸다고 나오는데 어디가 틀렸는지 도통 모르겠습니다.

(追記) (追記ここまで)

계속 틀렸다고 나오는데 어디가 틀렸는지 도통 모르겠습니다.

11478번 - 서로 다른 부분 문자열의 개수

khqwer 1년 전 0

다른 코드와 비교해봐도 차이를 모르겠습니다.

마구잡이로 한 O(n^2)의 결과와도 같은데 왜 답이 틀렸다고 나오는지 모르겠습니다.

use std::io;
fn count_distinct_substrings(s: &str) -> usize {
 let n = s.len();
 let sa = suffix_array(s);
 let lcp = lcp_array(s, &sa);
 let mut distinct_substrings = (n * (n + 1)) / 2;
 for &length in &lcp {
 distinct_substrings -= length;
 }
 distinct_substrings
}
fn suffix_array(s: &str) -> Vec<usize> {
 let n = s.len();
 let mut sa: Vec<usize> = (0..n).collect();
 let mut rank: Vec<usize> = s.bytes().map(|c| c as usize - b'a' as usize).collect();
 let mut k = 1;
 while k < n {
 sa.sort_by_key(|&i| (rank[i], if i + k < n { rank[i + k] } else { 0 }));
 let mut tmp = vec![0; n];
 tmp[sa[0]] = 0;
 for i in 1..n {
 if rank[sa[i]] == rank[sa[i - 1]]
 && (sa[i] + k < n && sa[i - 1] + k < n && rank[sa[i] + k] == rank[sa[i - 1] + k])
 {
 tmp[sa[i]] = tmp[sa[i - 1]];
 } else {
 tmp[sa[i]] = tmp[sa[i - 1]] + 1;
 }
 }
 rank = tmp;
 k *= 2;
 }
 sa
}
fn lcp_array(s: &str, sa: &[usize]) -> Vec<usize> {
 let n = s.len();
 let mut lcp = vec![0; n - 1];
 let mut rank = vec![0; n];
 for i in 0..n {
 rank[sa[i]] = i;
 }
 let mut l = 0;
 for i in 0..n {
 if rank[i] == n - 1 {
 continue;
 }
 let j = sa[rank[i] + 1];
 while i + l < n && j + l < n && s.as_bytes()[i + l] == s.as_bytes()[j + l] {
 l += 1;
 }
 lcp[rank[i]] = l;
 if l > 0 {
 l -= 1;
 }
 }
 lcp
}
fn main() {
 let mut input = String::new();
 io::stdin().read_line(&mut input).unwrap();
 let s = input.trim_end();
 let count = count_distinct_substrings(s);
 println!("{}", count);
}

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

계속 틀렸다고 나오는데 어디가 틀렸는지 도통 모르겠습니다.

khqwer 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말