Entre os algoritmos de busca de correspondência de strings, os dois mais famosos são o algoritmo KMP (Knuth-Morris-Pratt) e o algoritmo BM (Boyer-Moore). Ambos os algoritmos possuem tempos de busca lineares no pior caso. No entanto, na prática, o algoritmo KMP não é muito mais rápido que a função strstr() mais simples da biblioteca C, enquanto o algoritmo BM é frequentemente 3-5 vezes mais rápido que o algoritmo KMP (não praticado pessoalmente). No entanto, o algoritmo BM ainda não é o algoritmo mais rápido. Aqui está um algoritmo de busca, o algoritmo de domingo, que é mais rápido que o algoritmo BM.
A ideia do algoritmo de domingo é muito semelhante à ideia de caracteres ruins no algoritmo BM. A única diferença é que, depois que o algoritmo de domingo falha na correspondência, ele ocupa o caractere uma posição atrás da parte atual da sequência de destino que corresponde à sequência de padrão para fazer a correspondência de caracteres incorretos. Quando se descobre que a correspondência falha, é avaliado se o caractere no deslocamento atual + comprimento da string padrão + 1 (assumido como a posição K) na string pai existe na string padrão. Se existir, alinhe a posição com o caractere na string Pattern e, em seguida, combine desde o início, se não existir, mova a string Pattern para trás, alinhe-a com o caractere em k+1 da string pai e, em seguida, corresponder. Repita a operação acima até que seja encontrada ou a string pai seja encontrada. Escrevi um pequeno exemplo para implementar o seguinte algoritmo.
No código, dois algoritmos de correspondência de strings são implementados, um é o método Sunday e o outro é o método comum de mover um bit por vez. A comparação de eficiência dos dois é mostrada na função principal, ambos no nível de nanossegundos. . As etapas detalhadas do algoritmo foram adicionadas com comentários correspondentes no código. Em relação ao algoritmo BM, iremos comparar e analisar juntos na próxima vez que estiver vazio.
Copie o código do código da seguinte forma:
importar java.util.HashMap;
importar java.util.LinkedList;
importar java.util.List;
importar java.util.Map;
/**
* @autor Scott
* @data 28 de dezembro de 2013
* @descrição
*/
classe pública SundySearch {
String texto = nulo;
Padrão de string = nulo;
int PosPos atual = 0;
/**
* Lista das primeiras posições dos caracteres da substring correspondente
*/
List<Integer> matchedPosList = new LinkedList<Integer>();
/**
* Mapa de caracteres correspondentes, registra quais caracteres estão na string correspondente e o último deslocamento de cada caractere
*/
Map<Caracter, Inteiro> map = new HashMap<Caracter, Inteiro>();
public SundySearch(String texto, String padrão) {
este.texto = texto;
este.padrão = padrão;
this.initMap();
};
/**
* Ao combinar Domingo, é utilizado para armazenar a posição da última ocorrência de cada caractere no Padrão, na ordem da esquerda para a direita.
*/
private void initMap() {
for (int i = 0; i < padrão.comprimento(); i++) {
this.map.put(pattern.charAt(i), i);
}
}
/**
* Correspondência recursiva de string comum, se a correspondência falhar, avance uma posição
*/
public List<Integer> normalMatch() {
//Falha na correspondência, continue descendo
if (!matchFromSpecialPos(currentPos)) {
atualPos += 1;
if ((text.length() - currentPos) <padrão.length()) {
retornar correspondênciaPosList;
}
normalMatch();
} outro {
//Correspondência com sucesso, registro de localização
matchedPosList.add(currentPos);
atualPos += 1;
normalMatch();
}
retornar correspondênciaPosList;
}
/**
* Correspondência de domingo, assumindo que a posição do caractere K no Texto é: deslocamento atual + Comprimento da string do padrão + 1
*/
public List<Integer> sundayMatch() {
//Se nenhuma correspondência for bem-sucedida
if (!matchFromSpecialPos(currentPos)) {
// Se o caractere K em Text não aparecer na string Pattern, pule todo o comprimento da string Pattern.
if ((currentPos + padrão.comprimento() + 1) <text.comprimento()
&& !map.containsKey(text.charAt(currentPos + padrão.length() + 1))) {
currentPos += padrão.comprimento();
}outro {
// Se o caractere K em Texto aparecer na string Padrão, alinhe a posição do caractere K em Texto com a posição do último caractere K na string Padrão.
if ((currentPos + padrão.comprimento() + 1) > text.comprimento()) {
atualPos += 1;
} outro {
currentPos += pattern.length() - (Inteiro) map.get(text.charAt(currentPos + pattern.length()));
}
}
// Quando a partida for concluída, retorne o deslocamento inicial de todas as partidas bem-sucedidas.
if ((text.length() - currentPos) <padrão.length()) {
retornar correspondênciaPosList;
}
domingoMatch();
}outro {
//Se a partida for bem-sucedida, avança um bit e depois combina novamente
matchedPosList.add(currentPos);
atualPos += 1;
domingoMatch();
}
retornar correspondênciaPosList;
}
/**
* Verifique se a substring começando no deslocamento especificado do Texto corresponde ao Padrão
*/
public boolean matchFromSpecialPos(int pos) {
if ((text.length()-pos) <padrão.length()) {
retornar falso;
}
for (int i = 0; i < padrão.comprimento(); i++) {
if (text.charAt(pos + i) == padrão.charAt(i)) {
if (i == (padrão.comprimento()-1)) {
retornar verdadeiro;
}
continuar;
} outro {
quebrar;
}
}
retornar falso;
}
public static void main(String[] args) {
SundySearch sundySearch = novo SundySearch("olá ah Adolf adfsadfklf adf234masdfsdfdsfdsfdsffwerwrewrerwerwersdf2666sdflsdfk", "adf");
início longo = System.nanoTime();
System.out.println("NormalMatch:" + sundySearch.normalMatch());
System.out.println("NormalMatch:" + (System.nanoTime() - início));
começar = System.nanoTime();
System.out.println("SundayMatch:" + sundySearch.sundayMatch());
System.out.println("SundayMatch:" + (System.nanoTime() - início));
}
}