는 내가와 일치하는 패턴 피셔 & 패터슨 알고리즘을 이해하고 여기에 표시된 "틀리하지 않는다"생각 O ((n^2) (logm)) 시간에 2 차원 매칭을 풀기 위해 매칭하는 것. 이를 위해 "상관 없어요"기호는 각 문자열의 끝 또는 그와 비슷한 것으로 붙잡고이를 1 차원 문제로 변환해야합니다. 그것이 내가 정말로 이해하지 못하는 부분입니다. 나는 몇 가지 시도를했지만 어떻게 도움이되는지 알 수 없습니다.패턴 매칭으로 2D 매칭 문제를 해결하는 방법은 무엇입니까? <a href="http://u.cs.biu.ac.il/~amir/AlgII/fp-set1.html" rel="nofollow">http://u.cs.biu.ac.il/~amir/AlgII/fp-set1.html</a></p> <p>그러나, 나는 하나의 차원 "걱정하지 않는다"사용할 수 있습니다 이해로 :
따라서 "상관하지 마십시오"라는 1D 일치는 2D 일치를 해결하는 데 어떻게 도움이됩니까?
감사합니다.
편집 : 나는 그것을 얻는다고 생각합니다. 텍스트를 선형화해야합니다 (행을 연결). 패턴에 대해서도 동일하지만 각 행 다음에 n-m 개의 관리되지 않는 심볼이 추가되어야합니다 (패턴의 마지막 행 제외). 그러나 이것은 O ((n^2) (log (m^2))) 시간을 얻었고 이전에 언급 한 시간은 불가능하다고 생각합니다. 코멘트? 로그
참. 나는 그 사실을 알아 차리기에는 너무 압박감을 느꼈다. 결국, 저는이 시험에서 제가 공부하고 있던 문제였습니다. – shwartz