Supongo que desea una expresión regular que verifique toda la línea, y desea que acepte una cadena solo si cierta letra aparece menos de N veces en la cadena.
Mira, las expresiones regulares se llaman regulares, porque pertenecen a la clase de lenguajes regulares. Los idiomas regulares son algo limitados, pero su solicitud (aceptar algo solo si la letra aparece menos de N veces) está dentro de los límites.
Primero, echemos un vistazo al Autómata finito determinista que aceptaría dicha cadena:
- El emparejamiento PvP "perfectamente justo" daría como resultado una tasa de ganancia esperada del 50% para todos. Eso puede sentirse muy bajo (sesgo de confirmación, rayas malas). Además de PvP asincrónico, ¿hay alguna manera de aumentar el WR percibido de todos mientras se mantiene justo el MM?
- Cómo crear una ordenación rápida en C
- ¿Por qué el método de ordenación Javascript organiza los números de una matriz en orden ascendente con [código] (a - b) [/ código] y descendente con [código] (b - a) [/ código]?
- ¿Cuáles son algunas buenas ideas sobre proyectos en algoritmos y / o estructuras de datos?
- ¿Cuáles son los mejores recursos para aprender R? Tratando de construir mi propio algoritmo de predicción basado en datos anteriores que tengo en archivos csv y que solía ser un desarrollador de Ruby hace un par de años
Aquí “q” es la letra que queremos limitar, Σ es el alfabeto completo que estamos aceptando (por ejemplo, cualquier carácter). Σ – q es un alfabeto completo sin la letra. Los estados subrayados son estados aceptados. Aceptamos como máximo 5 q’s.
Puede ver que DFA para este problema es realmente simple: solo dibuja N + 1 estados. Cada estado “cuenta” las ocurrencias de la letra (“q”) en la cadena que estamos procesando. Comenzamos en 0, porque inicialmente hemos visto 0 letras (“q” s). Si alcanzamos el estado N + 1, sabemos que la letra apareció demasiadas veces, por lo que dejamos de aceptar (el estado N + 1 es el único estado que no es aceptado. No puede salir de este estado) .
Ahora volvemos a crear una expresión regular. Después de mirar este DFA, creo que es más fácil ver cómo podríamos querer crear una expresión regular de este tipo (en la expresión regular, nuestra letra es “h” y nuestra N es 6):
^ ([^ h] * h) {0,6} [^ h] * $
Primero tenemos “^”. Esto significa que queremos asegurarnos de tener el comienzo de nuestra cadena. De lo contrario, obtendríamos coincidencias parciales (por ejemplo, en la cadena “hhhhhhhhho”, “o” coincide con nuestra expresión regular).
A continuación, tenemos el grupo “([^ h] * h)”. Esto significa que queremos ver cualquier cantidad de caracteres que no sean h. Entonces, por ejemplo, podemos aceptar “h”, “addh” u “ooh”, pero no cualquier cosa que tenga más de una h, por ejemplo, “hoh”.
Luego, tenemos “{0,6}” que nos dice que el grupo que acabamos de mencionar debe aparecer al menos 0 veces (por lo que también aceptamos cadenas vacías), pero como máximo 6 veces.
Finalmente, tenemos [^ h] * nuevamente. Esto es para permitir que la cadena termine en cualquier letra, no solo h.
Y después de eso, terminamos la línea con $.
Tal expresión regular es bastante simple y no requiere búsquedas.
