http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
근사 패턴 매칭 문제에 대한 단방향 선형 시스톨릭 배열 알고리즘
김길화(Kil-hwa Kim),장직헌(Jik-Hyun Chang) 한국정보과학회 1991 한국정보과학회 학술발표논문집 Vol.18 No.2
문자열 편집(String edit) 문제의 특별한 유형인 근사 패턴 매칭(Approximate Pattern Matching)문제는 한 문자열에서 다른 문자열(패턴)에 근사한 부문자열(substring)을 구하는 문제이고 최대 공통 부순서(Longest Common Subsequence) 문제는 두 문자열이 공통으로 가지는 부순서 중에서 최대 길이의 부순서를 찾아내는 문제이다. 본 논문은 단방향의 선형 시스톨릭 배열(One-Way Linear Systolic Array)에서 선형 시간내에 위 문제들을 해결하는 병렬 알고리즘을 설계한다. 특히, LCS문제는 최적값뿐 아니라 LCS 그 자체도 구한다.