문자열에는 서브 시퀀스가 ​​있지만 일반적으로 모두 고유하지는 않습니다. 하위 시퀀스의 최대 빈도를 찾는 복잡성은 무엇입니까?2엔

$2^n$

예를 들어 문자열 “subsequence”에는 7 개의 하위 시퀀스 “sue”가 포함되며 최대 값입니다.

http://ideone.com/UIp3t의 샘플 무차별 코드

관련 구조 정리가 있습니까? 이 두 가지 모두 거짓 으로 판명되었습니다 .

• 최대 주파수 하위 시퀀스 중 가장 긴 고유
• 임의의 최대 길이 – 주파수 의 서브 단봉에서k케이
  $\mathrm{케이}$

  $k$케이

  $\mathrm{케이}$

  $k$

아마도 관련 링크 :

• 세 개의 고유 하위 시퀀스 계산 http://11011110.livejournal.com/254164.html∈ P
  $\in \mathbf{피}$

  $\in \mathbf{P}$

• 여러 소스에 대한 관련 콘테스트 문제 http://www.spoj.pl/problems/CSUBSEQS/
• 관련 논문 http://dx.doi.org/10.1016/j.tcs.2008.08.035

10 일 후 수정 : 살펴 주셔서 감사합니다. 이것이 멋진 다항식 시간 해결할 수있는 프로그래밍 콘테스트 문제가 될지 궁금했습니다. 나는 생각하지 않지만 나중에 다시 생각하기를 바랍니다.

답변