4개의 댓글이 있습니다.
-
-
wookayin -
첫 번째 질문의 답은 - 저렇게 suffix array를 만든 뒤 인접한 두 개만 보면 됩니다. 어차피 두번 출현한 substring이라면 suffix array상에서 인접해서 두 번 나타날 것이므로 2번 출현한지 여부를 알 수 있습니다.
두 번째 질문의 답은 - 어떤 substring은 어떤 suffix의 prefix이므로, 인접한 것 중 공통된 prefix만을 보면 됩니다.예를들어 br 라는 substring은, bra와 bracadabra에 공통적으로 나타나므로 커버가 되죠. 그런데 어차피 찾고싶은 것은 가장 긴 것이기 때문에, suffix array 상에서 인접한 suffix들만 비교해보면 됩니다.
13년 전 link
-
-
-
freedomJ -
suffix array에서 인접한 2개만 보면 된다는 말씀은 a와 abra, abra와 abracadabra, abracadabra와 adabra.... .... .... ra와 racadabra 이렇게 보라는 말씀같은데,
a와 abra를 본다는건 구체적으로 알려주셨으면 합니다..;; 아직 미궁속이네요 ..;두번째 질문답변에 대한 추가질문은... 음.. 예외가 안생기는가 하는점입니다. bra가 br을 포함하기때문이라고 하셨는데, 언급한 예제에서는 아니지만, bra가 한번만 출현하고 br은 2번 출현하는 경우도 있지 않을까 하는 생각입니다..;
13년 전 link
-
-
-
Taeyoon_Lee -
string a="abra";
string b="abracadabra";
int c=0;
while(c < a.size() && c < b.size() && a[c]==b[c])
c++;이렇게 해서 c의 값을 보시라는 말씀입니다.
예외의 경우는 있을 수 없습니다. 우리가 찾는 답이 되는 문자열이 입력에서 [L1,R1] [L2,R2] 두 부분에서 찾을 수 있다고 해보죠. (예를 들어 입력이 aaaaa라고 하면 [0,3] [1,4] 가 될 수 있겠죠.)
suffix array에는 L1에서 시작하는 문자열도 있을 것이고, L2에서 시작하는 문자열도 있을 것입니다. suffix array에는 모든 인덱스에서 시작하는 문자열이 다 들어가니까요. 그리고 그것들이 sorting된 상태에서는 항상 이 두 문자열이 인접하게 됩니다.우리가 찾는 정답이 "abcde"라고 가정하고, suffix array를 상상해봅시다.
.
..
abcde....
abcde....
..
.suffix array에는 이런 형태가 반드시 나올 겁니다. 만약 위의 형태에서 두 abcde 사이에 어떤 다른 문자열이 있다고 하면 그 문자열은 반드시 abcde로 시작하는 문자열이어야 합니다. sorting 되었으니까요.
abcde....
abcdf.... (x)
abcde....abcde....
abcdc.... (x)
abcde....충분한 답변이 되었을지 모르겠네요. 최대한 쉽게 설명하려고 했는데, 오히려 역효과가 난 건 아닌지..ㅜㅜ
13년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
freedomJ
이틀내내 붙잡고 혼자 끙끙 거리다가 끝내 구글링하고, 여기까지 오게됬습니다.;; 처음에는 검색만 하려다가, 채점서버도 구축되어있고.. 질문답변도 하기좋을것같아 가입했습니다. ^^ ,,
답은 나오는데 채점서버가 계속 TLE를 주네요 ㅠ, 실행속도 개선해서 랜덤한 5000개 이내의 string 100개를 대상으로 실행속도가
디버그모드 20초, 릴리즈모드 2.9초가 나오네요 ㅠ.
가입인사는 이정도로하고...
ACM ICPC problem B. Editor 문제인데.. (수정: 아,, 서울지역 본선문제입니다. 문제번호 p3901)
문제를 간략히 요약하면,
input 은 길이 5000이하의 string S가 주어지면, S에서 2번이상 나타나는 Longest Substring의 길이를 찾는 문제입니다.
(2번이상 나타난다는 것은 중복이 허용됩니다. 예를 들어 S가 abcabcabc라면 Longest substring은 abcabc가 되서 답은 6이 됩니다.
검색해서 문제해설을 찾아보니... suffix array를 사용해서 문제를 풀면 쉬울거라고 하셨는데,
기존에 suffix array가 뭔지 몰랐지만, 설명으로 이해는 했습니다. 하지만 문제에 어떻게 적용해서 풀어야 할지 감이 오질 않아서 이렇게 질문합니다.
S가 abracadabra라고 하면...
abracadabra 의 suffix array는
abracadabra
bracadabra
racadabra
acadabra
cadabra
adabra
dabra
abra
bra
ra
a
이런식의 substring을 담는 array이고 sorting을 한 array로 알고있습니다. sorting을 하면
a
abra
abracadabra
acadabra
adabra
bra
bracadabra
cadabra
dabra
ra
racadabra
이렇게 되는데, 이 정보로 S에서 2번 출현한 여부는 어찌 알 수 있는지...
그리고 substring br, dab 등등에 대해서는 고려를 안하게되는데 이것은 어떻게 cover하는지가 궁금합니다.
제가 알고리즘을 체계적으로 알지못해, 질문이 좀 정신없네요.;
13년 전