두 문자열에서 같은 순서로 문자 집합

Question

두 개의 문자열이 있습니다. 첫 번째 기본 문자열과 다른 하나를 입력 문자열로 호출합시다. 기본 문자열의 몇 문자가 입력 문자열 안에 순서대로 있는지 알아보기 위해 알고리즘을 고안하고 있습니다. 즉, 기본 문자열의 모든 문자가 입력 문자열에 나타날 수있는 것은 아니지만 문자 수에 상관없이 순서대로 있어야합니다 (기본 문자열에있는 것처럼) 내부 문자열의 일치 비율을 알아야합니다. 입력 문자열

예 :

base string: abcd 
input string: *a*b*c*d* 
output: 100% 

base string: abcd 
input string: *b*c*d* 
output: 75% 

base string: abcd 
input string: *a*c*d* 
output: 75% 

base string: abcd 
input string: *a*c*b*c*d* 
output: 75% (*a*c*d* or *b*c*d*) 

base string: abcd 
input string: *b*a*d*b*c*d* 
output: 100% (*a*b*c*d* is found) 

Answer 1

보기에 생각하면, 이것은 일반적인 LCS 문제입니다. 백분율은 LCS와 입력 문자열/기준 문자열의 길이의 비율로 알 수 있습니다.

구현에 대해서는 Hirschberg 알고리즘을 사용하고 싶습니다.