4

Diferentemente do match() que procura por uma ocorrência de uma linguagem y no início da string, o find() faz uma busca por y dentro dessa string. Eu poderia utilizar o algoritmo de Knuth-Morris-Pratt para procurar por a primeira ocorrência n0, n1, ..., n de X(string) em S(string) em complexidade O(n+k), sendo n o tamanho de X e k o tamanho de S, mas isso é inviável na implementação do autômato de busca por causa das transições de estado (creio eu, pois o algoritmo apenas olha ao início da string, eu preciso implementá-lo para que uma determinada linguagem, possa ser encontrada tanto no início/meio/fim).

Alguém pode me trazer uma luz sobre isso?

8
  • 1
    Não estou entendendo a sua pergunta direito. Um autômato finito determinístico vai processar a string de entrada em tempo O(n) e o algoritmo KMP é eficiente justamente pq ele constrói um autômato finito ao invés de fazer uma busca ingênua...
    – hugomg
    Commented 10/08/2014 às 5:05
  • Sim, isso é óbvio, o problema é MANUSEAR OS ESTADOS da DFA/NFA da linguagem que eu estou buscando dentro de S. O meu problema é esse, não faço a menor ideia de como implementar isso. Commented 10/08/2014 às 17:18
  • 2
    Achou alguma solução? Poste como resposta para ajudar outras pessoas.
    – Maniero
    Commented 14/10/2014 às 0:23
  • 2
    Você quer encontrar uma string fixa dentro de outra string, ou achar uma regex dentro da string? E perguntar "como é implementada" sem especificar uma linguagem/plataforma é complicado de responder, pois cada uma pode fazer isso de uma forma diferente (existem diversos métodos de busca em string, bem como diversos métodos de casamento de padrão, e nem sempre o "mais eficiente" - se é que existe - é usado na prática, por razões que variam caso a caso).
    – mgibsonbr
    Commented 11/11/2014 às 9:44
  • 1
    Porque não construir o clássico DFA/NFA para .*expressao-regular ?
    – JJoao
    Commented 16/03/2017 às 9:21

2 Respostas 2

1
+50

Construa um parser LR a partir das produções:

s -> .*minha_regex
minha_regex -> sua regex original

Quando a produção minha_regex for reduzida pela primeira vez, você terá achado.

Converter partes da regex em produções é relativamente símple:

  • a -> x* é o mesmo que:

    a -> ε
    a -> a x
    
  • a -> x | y é o mesmo que:

    a -> x
    a -> y
    
  • a -> (x | y) z* é o mesmo que:

    a -> a0 a1
    a0 -> x
    a0 -> y
    a1 -> ε
    a1 -> a1 z
    
1
  • Grande ideia, Miguel. Commented 11/11/2014 às 17:50
0

Regex - EM JAVA (você não disse a linguagem, espero que ajude!)

As expressões regulares(regex), é um recurso onde podemos estar fazendo busca com apenas simples caracteres (sequência de letras, dígitos, etc) ou com metacaracteres. Logo, para utilizarmos tais vantagens precisamos obviamente, indicar uma fonte e os caracteres de buscas.

De Matcher os métodos: find(), start(), group(), end();

Temos como fonte: mouse da cor azul. Logo, quero encontrar onde estar a palavra cor, na nossa frase(em negrito). E agora!?

import java.util.regex.Matcher; 
import java.util.regex.Pattern; 

public class Regex { 

public static void main(String[] args) { 

String fonte = “mouse da cor azul”; 

String queremosIsso = “cor”; 

/*
* Nesse momento obteremos uma instância de Pattern, através do * método 
* static compile(String regex), o qual recebe uma String que é a 
* expressção regular 
*/ 
Pattern p = Pattern.compile(queremosIsso); 

/* 
* Aqui, através da instancia de Pattern, chamando o método * matcher() e passando a fonte de busca 
*/ 

Matcher m = p.matcher(fonte); 

//Ligando o motor 
while (m.find()) { 

//Obtendo o inicio do que foi encontrado 
System.out.println(m.start()); 

} 

} 

} 

Ao executarmos este código, obteremos como resposta 9(nove). Mas, por que 9?

Primeiro vamos ver o que acontece.

Após termos obtidos as instancias de Pattern e Matcher, em um loop(while) chamamos o método m.find(). Ao chamarmos este cara, o motor regex é disparado, ou seja, a tarefa de busca é efetivamente iniciada. Vale lembra que o motor regex, executa a busca da esquerda para a direita e ao passo que ele encontrar uma ocorrência, está não participara mais do processo de busca. Logo abaixo no código, chamei o método m.start(). Esse método retorna um inteiro, onde este representa, o índice inicial de cada sequencia encontrada, que neste caso seria 9(nove). Lembrabdo que começa do zero. Abaixo segue as letras e seus índices(onde estiver duas aspas sem conteúdo, representam espaços).

0-m 1-o 2-u 3-s 4-e 5-’ ‘ 6-d 7-a 8-’ ‘ 9-c

mouse da cor azul

Existe também como falei no início, o método group(). Este é responsável por trazer o grupo de caracteres que foi encontrado na busca.

Ex: //Ligando o motor

while (m.find()) { 

//Obtendo o inicio do que foi encontrado 

System.out.println(m.start() +” “+ m.group() +” “+ m.end()); 

} 

Terá como saída: 9 cor 12

Em seguida o método end(), onde este é a contra partida de start( ), trazendo o índice do ultimo caracter encontrado, porém esse o índice inicia no um(1).

Fonte:http://www.devmedia.com.br/introducao-a-regex/15597

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .