가중 문자열은 알파벳 Σ와 각 문자에 가중치를 정해 주는 함수 f 위에서 정의한다. 문자열 s의 가중치는 s를 이루는 모든 문자의 가중치를 더한 값이다.
생물정보학의 여러 문제는 가중 문자열에 대한 문제로 형식화된다. 단백질 질량 분석이 그런 예다. 아미노산 하나를 서로 다른 문자 하나로 나타내면, 단백질은 그 단백질을 이루는 아미노산에 대응하는 문자열이 된다.
단백질 질량 분석을 쓰는 곳 가운데 하나가 데이터베이스 검색이다. 단백질을 나타내는 문자열을 여러 부분 문자열로 나누고, 각 부분 문자열의 질량을 구한 다음, 그 질량 목록을 단백질 데이터베이스와 대조한다. 문자열이 길어지면 가능한 부분 문자열이 매우 많아지므로, 몇 개를 고르느냐가 결과의 품질을 좌우한다.
생명공학 연구소에서 인턴을 시작한 카를로스는 첫날 과제를 하나 받았다. 문자열 s가 주어질 때, 연속한 문자로 이루어진 비어 있지 않은 모든 부분 문자열의 가중치를 구하고, 그 값 중 서로 다른 것이 몇 개인지 세는 것이다.
s는 알파벳 소문자로만 이루어지고, 소문자 26개의 가중치는 모두 다르다. a는 1, b는 2, 같은 방식으로 z는 26이다. 가장 긴 입력도 여유 있게 처리하는 풀이를 작성하라.
cho.sh