문자열 일치 검색 알고리즘 중 가장 유명한 두 가지 알고리즘은 KMP 알고리즘(Knuth-Morris-Pratt)과 BM 알고리즘(Boyer-Moore)입니다. 두 알고리즘 모두 최악의 경우 선형 검색 시간을 갖습니다. 그러나 실제로 KMP 알고리즘은 가장 간단한 C 라이브러리 함수 strstr()보다 훨씬 빠르지 않은 반면, BM 알고리즘은 KMP 알고리즘보다 3~5배 빠른 경우가 많습니다(개인적으로 실행하지는 않음). 그러나 BM 알고리즘은 아직 가장 빠른 알고리즘은 아닙니다. 여기에는 BM 알고리즘보다 빠른 검색 알고리즘인 Sunday 알고리즘이 있습니다.
Sunday 알고리즘의 아이디어는 BM 알고리즘의 Bad Character 아이디어와 매우 유사합니다. 유일한 차이점은 일요일 알고리즘이 일치에 실패한 후 잘못된 문자 일치를 수행하기 위해 패턴 문자열에 해당하는 대상 문자열의 현재 부분 뒤의 문자 한 위치를 사용한다는 것입니다. 일치에 실패한 것으로 확인되면 부모 문자열의 현재 오프셋 + 패턴 문자열 길이 + 1(K 위치로 가정)의 문자가 패턴 문자열에 존재하는지 판단합니다. 존재하면 Pattern 문자열의 문자와 위치를 맞춘 후 처음부터 일치시키고, 존재하지 않으면 Pattern 문자열을 뒤로 이동하여 상위 문자열의 k+1에 있는 문자와 정렬한 다음 성냥. 위의 작업을 찾거나 상위 문자열을 찾을 때까지 반복합니다. 다음 알고리즘을 구현하기 위해 작은 예제를 작성했습니다.
코드에는 두 가지 문자열 일치 알고리즘이 구현되어 있습니다. 하나는 Sunday 방법이고 다른 하나는 한 번에 한 비트씩 이동하는 일반적인 방법입니다. 두 가지의 효율성 비교는 둘 다 나노초 수준에서 main 함수에 표시됩니다. . 알고리즘의 세부 단계가 코드에 해당 주석과 함께 추가되었습니다. BM 알고리즘에 관해서는 다음번에 비어있을 때 함께 비교 분석해보도록 하겠습니다.
다음과 같이 코드 코드를 복사합니다.
java.util.HashMap 가져오기;
java.util.LinkedList 가져오기;
java.util.List 가져오기;
java.util.Map 가져오기;
/**
* @author 스캇
* @date 2013년 12월 28일
* @설명
*/
공개 클래스 SundySearch {
문자열 텍스트 = null;
문자열 패턴 = null;
int currentPos = 0;
/**
* 일치하는 하위 문자열의 첫 번째 문자 위치 목록
*/
List<Integer> matchPosList = new LinkedList<Integer>();
/**
* 일치하는 문자 맵, 일치하는 문자열에 어떤 문자가 있는지 기록하고 각 문자의 마지막 변위를 기록합니다.
*/
Map<Character, Integer> map = new HashMap<Character, Integer>();
public SundySearch(문자열 텍스트, 문자열 패턴) {
this.text = 텍스트;
this.pattern = 패턴;
this.initMap();
};
/**
* 일요일 일치시 패턴 내 각 문자의 마지막 발생 위치를 왼쪽에서 오른쪽으로 저장하는데 사용됩니다.
*/
개인 무효 initMap() {
for (int i = 0; i < 패턴.길이(); i++) {
this.map.put(pattern.charAt(i), i);
}
}
/**
* 일반 문자열 재귀 일치, 일치에 실패하면 한 단계 전진
*/
공개 목록<정수> NormalMatch() {
//일치에 실패했습니다. 계속해서 아래로 내려갑니다.
if (!matchFromSpecialPos(currentPos)) {
현재Pos += 1;
if ((text.length() - currentPos) < 패턴.길이()) {
matchPosList를 반환합니다.
}
NormalMatch();
} 또 다른 {
//성공적으로 일치합니다. 위치를 기록합니다.
matchPosList.add(currentPos);
현재Pos += 1;
NormalMatch();
}
matchPosList를 반환합니다.
}
/**
* 일요일 일치, Text의 K 문자 위치가 다음과 같다고 가정: 현재 오프셋 + 패턴 문자열 길이 + 1
*/
공개 목록<Integer> sundayMatch() {
// 일치하지 않는 경우
if (!matchFromSpecialPos(currentPos)) {
// Text의 K 문자가 Pattern 문자열에 나타나지 않으면 전체 Pattern 문자열 길이를 건너뜁니다.
if ((currentPos + 패턴.길이() + 1) < 텍스트.길이()
&& !map.containsKey(text.charAt(currentPos + Pattern.length() + 1))) {
currentPos += 패턴.길이();
}또 다른 {
// Text의 K 문자가 Pattern 문자열에 나타나면 Text의 K 문자 위치를 Pattern 문자열의 마지막 K 문자 위치에 맞춥니다.
if ((currentPos + Pattern.length() + 1) > text.length()) {
현재Pos += 1;
} 또 다른 {
currentPos += 패턴.길이() - (정수) map.get(text.charAt(currentPos + 패턴.길이()));
}
}
// 일치가 완료되면 성공한 모든 일치의 초기 변위를 반환합니다.
if ((text.length() - currentPos) < 패턴.길이()) {
matchPosList를 반환합니다.
}
sundayMatch();
}또 다른 {
//성공적으로 일치하면 한 비트 전진한 후 다시 일치시킵니다.
matchPosList.add(currentPos);
현재Pos += 1;
sundayMatch();
}
matchPosList를 반환합니다.
}
/**
* Text의 지정된 오프셋에서 시작하는 하위 문자열이 Pattern과 일치하는지 확인합니다.
*/
공개 부울 matchFromSpecialPos(int pos) {
if ((text.length()-pos) < 패턴.길이()) {
거짓을 반환;
}
for (int i = 0; i < 패턴.길이(); i++) {
if (text.charAt(pos + i) == 패턴.charAt(i)) {
if (i == (pattern.length()-1)) {
사실을 반환;
}
계속하다;
} 또 다른 {
부서지다;
}
}
거짓을 반환;
}
공개 정적 무효 메인(String[] args) {
SundySearch sundySearch = new SundySearch("안녕하세요 아돌프 adfsadfklf adf234masdfsdfdsfdsfdsffwerwrewrerwersdf2666sdflsdfk", "adf");
긴 시작 = System.nanoTime();
System.out.println("NormalMatch:" + sundySearch.normalMatch());
System.out.println("NormalMatch:" + (System.nanoTime() - 시작));
시작 = System.nanoTime();
System.out.println("SundayMatch:" + sundySearch.sundayMatch());
System.out.println("SundayMatch:" + (System.nanoTime() - 시작));
}
}