유사도

바이트만(Byteman)은 문자열, 패턴, 텍스트 등과 관련된 알고리즘을 설계하는 컴퓨터 과학자입니다. 이번 과제는 패턴과 텍스트의 유사도(similarity) 를 계산하는 도구를 만드는 것입니다.

패턴과 텍스트가 주어지면, 패턴의 각 글자가 텍스트의 한 글자와 대응되도록 여러 방법으로 정렬(align)할 수 있습니다. 여기서는 구멍(hole)이 없는 정렬만 생각합니다. 즉, 패턴은 항상 텍스트에서 패턴과 길이가 같은 연속된 부분과 맞대어집니다. 이러한 정렬 하나에 대해, 패턴의 글자와 대응되는 텍스트의 글자가 서로 같은 위치의 개수를 셀 수 있습니다. 가능한 모든 정렬에 대해 이 개수를 모두 더한 값을 패턴과 텍스트의 유사도라고 합니다.

아래 그림은 패턴 abaab 와 텍스트 aababacab 사이의 유사도를 계산하는 과정을 보여줍니다.

패턴과 텍스트가 주어졌을 때, 그 유사도를 계산하세요.

입력은 두 줄로 이루어집니다. 첫째 줄에는 소문자 알파벳으로만 이루어진 비어 있지 않은 문자열, 곧 패턴이 주어집니다. 둘째 줄에는 소문자 알파벳으로만 이루어진 비어 있지 않은 문자열, 곧 텍스트가 주어집니다. 패턴의 길이는 텍스트의 길이보다 크지 않습니다. 텍스트의 길이는 2 000 000 이하입니다.

패턴과 텍스트의 유사도를 한 줄에 출력합니다.