문자열에서 부분 문자열 집합을 효율적으로 찾습니다.

문자열이 "ab", "cd" and "ef" 인 것으로 가정합니다.
(우리가 긴 문자열이 있다고 가정하자 이제
즉 any of {"abcdef","abefcd","efabcd","efcdab","cdefab","cdabcf"}
, 위의 문자열 순열은 우리가 검색 할 문자열을 가정하자 우리는 거기에 위의 세트에서 문자열 중 하나를 찾으려면 약간의 경우를 단순화하고 주 문자열에있는 하위 문자열 중 하나만 발생한다고 가정).
예 :문자열에서 부분 문자열 집합을 효율적으로 찾습니다.

Main string: abcdghefcdabgh 
Substring:   efcdab

이 경우 검색을 수행하는 가장 효율적인 방법은 무엇입니까? 무차별 대입 (brute force)을 수행하고 각각의 가능한 하위 문자열을 검색하는 것은 매우 비효율적입니다.
다중 패턴 검색을위한 Rabin-Karp는 내 마음에 오는 한 가지 방법입니다. 그러나 나는 그 때 매우 효율적인 해시 함수가 무엇인지 확신 할 수 없다.

출처

2011-11-01 eku

[위키]에 의해 기술 된 라빈 - 카프 롤 해시 (잘못 무엇 http://en.wikipedia.org/wiki/ 롤링 _ 하쉬)? –

당신이 묘사 한 특정한 경우에, 원하는 길이의 검색 문자열의 각 부분 문자열을 검사하는 것은 비효율적 인 것 같지 않습니다 (검색 문자열 길이 n에 대해 O (n)이 있음) 그리고 이것이 대상인지 여부를 확인하는 것은 비효율적 인 것 같습니다 끈. 대상 문자열 집합이 작 으면 O (m)에 해시 테이블을 만들 수 있습니다 (m은 대상 문자열의 개수 임) ...그렇지 않으면, 어떤 종류의 검색 트리 또는 뭔가를 만들 수 있습니다. 나는 당신이 O (n + m)보다 더 잘 할 수 있다고 어떻게 생각하는지 모르겠다. – Patrick87

@robmayoff 잘 그게 아무것도 잘못 됐어. 나는 단지 내가 누락 된 더 나은 방법을 알고 싶다. :) – eku

"ab"를 검색하고 +1 또는 -1에서 "cd"또는 "ef"를 찾고 전체 순열이 발견 될 때까지 계속하십시오.

예 :

사용 "ab", "cd", "ef"
"asjkdnjdnaboidnabefcdasdnmk"에서

"ab"의

첫 번째 인스턴스 따라서, 9에 있습니다 :

거기에서

lowerFound = 9 
upperfound = 11 \\ found index + length of found string

당신은 순열의 다른 일치한다는 것을 알고있다 lowerfound 이전이거나 upperfound 이상일 수 있으므로 양면을 확인하십시오. 예 :
dn ab oi 따라서, 어떤 경기를 포함 버리고 나는이 작업을 수행하는 프로그램을 공식화 한 15

lowerFound = 15 
upperfound = 17 
search for "cd" or "ef" at 15-length or 17 
found "ab"+"ef" 

lowerFound = 15 
upperfound = 19 
search for "cd" at 15-length or 19 
found "abef"+"cd" 

return

에서 다음 "ab"을 찾을 수 있지만, 그것은 현명한 매우 큰 라인, 그래서 내가 넣었습니다하지 않습니다 그것 right here, 비판이 방법을 자유롭게 느낀다.
최악의 경우를 줄이려면 "ababababababababcdef" 색인을 이미 메모리에 보관하는 것이 좋습니다.

출처

2011-11-01 05:08:29 Serdalis