Aho-Corasick과 단일 차원 KMP의 조합을 사용하여 2 차원 검색의 문제를 해결하려고했지만 더 빨리해야합니다.2 차원 KMP를 구현하는 방법에 대한 논문이나 설명이 있습니까?
정교하게 말하면, 크기가 n1 * n2 인 행렬 A를 가지며, 크기가 m1 * m2 인 더 작은 행렬 B를 모두 찾고 싶습니다. 그리고 그 행렬을 O (n1 * n2 + m1) * m2) 가능하다면. 예를 들어
:
A = a b c b c b
b c a c a c
d a b a b a
q a s d q a
및
B = b c b
c a c
a b a
말의 인덱스를 반환해야합니다 알고리즘,이 경우에 반환해야합니다 경기의 왼쪽 위 모서리 (0,1) 및 (0,3)이다. 어커런스가 겹칠 수 있습니다.
방금 전에 만난 Baker-Bird algorithm이라는 알고리즘이 있습니다.이 알고리즘은 2 차원으로 KMP를 부분적으로 일반화 한 것으로 보입니다. 서브 루틴으로 두 알고리즘을 사용합니다. 즉, Aho-Corasick algorithm (자체는 KMP의 일반화)과 KMP 알고리즘을 사용하여 패턴에 대한 2 차원 격자를 효율적으로 검색합니다.
나는 이것이 당신이 찾고있는 것이지 확실하지 않지만 잘하면 도움이된다.
나는 그 중 하나를 시도했는데 너무 느리고 다른 것을 필요로한다. –
"너무 느리다"는 것은 무엇을 의미합니까? 알고리즘이 구현이 아닌 범인이라고 확신합니까? 또한 작업하는 격자가 얼마나 큰가요? – templatetypedef
너무 느림 : 블랙 박스 테스트를 사용하고 있습니다. 즉, 테스트 한 데이터를 사용할 수 없습니다. 그것은 온라인 문제, 내 대답을 제출하고 내 솔루션은 rabin karp를 사용하여 0.37 초, 나는 앞에서 언급 한 접근법을 사용하여 그것을 시도하고 그것을했다 .82. .08 (문제와 시간을 해결 한 사람들의 이름 목록을 볼 수 있습니다)에서 그것을 할 수 있었던 누군가가 있습니다. 그리고 나는 거기에 가려고했습니다. –
확장 질문. 문제가 정확히 무엇입니까? 2D 문자 배열이 있는데, 수직 또는 수평 단어를 찾고 싶습니까? – maniek
@ maniek- 나는 OP가 다른 2D 그리드의 문자 안에서 2D 그리드를 검색하려고한다고 생각합니다. – templatetypedef