Encontrar subcadenas en una cadena es uno de los principales desaf os que enfrentan los desarrolladores en el lenguaje de programaci n C. es Importante poder encontrar las subcadenas que necesitamos de manera eficiente en grandes datos de texto para garantizar que el programa funcione de manera r pida y eficiente. En este art culo, veremos varias formas de implementar un algoritmo de b squeda de subcadena en una cadena utilizando el lenguaje C.
Una de las formas m s f ciles y populares de encontrar una subcadena en una cadena es usar la funci n strstr incorporada. Esta funci n le permite encontrar la primera aparici n de una subcadena en una cadena y devuelve un puntero al comienzo de la subcadena encontrada, o NULL si no se encuentra la subcadena. Pero tenga en cuenta que esta funci n solo funciona con caracteres, no con bytes, por lo que su uso est limitado a caracteres ASCII.
Ejemplo de uso de la funci n strstr:
const char * str =" ejemplo de cadena de texto";
const char * substr = "textual";
const char* result = strstr(str, substr);
Si se encuentra una subcadena, la variable result apuntar a la primera aparici n de la subcadena en la cadena. De lo contrario, la variable result contendr un valor nulo. A continuaci n, podemos usar el puntero result para las acciones que necesitamos, por ejemplo, para Mostrar una subcadena encontrada o realizar operaciones adicionales sobre ella.
- Subcadena y su significado en la programaci n C
- Algoritmos b sicos para encontrar subcadenas en una cadena
- 1. B squeda directa (fuerza bruta)
- 2. Algoritmo De Knuth-Morris - Pratt
- 3. - (Rabin-Karp)
- 4. - (Boyer-Moore)
- 5. - - (Boyer-Moore-Horspool)
- 6. - (Aho-Corasick)
- 7. - - (Ultra-Boyer-Moore)
- brute-force
- - -
- -
- Ejemplos de c digo de b squeda de subcadenas en una cadena en C
- Comparaci n y selecci n del algoritmo ptimo de b squeda de subcadenas en C
- 1. B squeda lineal
- 2. Algoritmo de Knuth-Morris-Pratt (CMP)
- 3. Algoritmo De Boyer-Moore
- 4. Algoritmo De Rabin-Karp
- 5. rbol de sufijos
- Pregunta-respuesta
- C mo puedo encontrar una subcadena en una cadena usando C?
- C mo encuentro todas las apariciones de subcadenas en una cadena en C?
- C mo encontrar una subcadena en una cadena, ignorando may sculas y min sculas en C?
- C mo encuentro el ndice de la primera aparici n de una subcadena en una cadena en C?
Subcadena y su significado en la programaci n C
Una subcadena es una secuencia de caracteres contenida en una cadena dada. La b squeda de subcadenas en una cadena es una de las operaciones m s comunes en la programaci n C.
En la programaci n C, hay varias formas de buscar una subcadena en una cadena:
- , proporcionan m todos convenientes para encontrar subcadenas en una cadena.
- Algoritmos de b squeda: Adem s de las funciones est ndar, se pueden usar varios algoritmos de b squeda de subcadenas, como el algoritmo de Knuth-Morris-Pratt (KMP), el algoritmo de Boyer-Moore (BM) y el algoritmo de Rabin-Karp.
- Funciones propias: Tambi n puede implementar su funci n de b squeda de subcadena en una cadena, bas ndose en el conocimiento de los algoritmos de b squeda b sicos.
Encontrar una subcadena en una cadena puede ser til para realizar una variedad de tareas. Por ejemplo, puede usarlo para:
- Comprobar la presencia de un texto espec fico en una l nea;
- Extraer datos espec ficos de una cadena;
- Sustituci n de una subcadena por otra;
- Dividir una cadena en subcadenas.
Es importante recordar que en la programaci n C, las cadenas se representan como matrices de caracteres, y una subcadena tambi n es una matriz de caracteres. Encontrar una subcadena en una cadena requiere definir la posici n inicial y la longitud de la subcadena, as como los m todos de comparaci n de caracteres. El uso adecuado de las funciones y algoritmos de b squeda de subcadenas le ayudar a trabajar eficazmente con datos de texto en la programaci n C.
Algoritmos b sicos para encontrar subcadenas en una cadena
Encontrar una subcadena en una cadena es una tarea com n cuando se trabaja con texto. Hay varios algoritmos b sicos que se pueden usar para resolver esta tarea.
1. B squeda directa (fuerza bruta)
El algoritmo m s simple para encontrar una subcadena es comparar secuencialmente cada car cter de cadena con cada car cter de la subcadena buscada. Si los caracteres coinciden, se pasa al siguiente car cter de ambas cadenas, de lo contrario se pasa al siguiente car cter de la cadena.
2. Algoritmo De Knuth-Morris - Pratt
El algoritmo de Knuth-Morris-Pratt utiliza informaci n adicional sobre las coincidencias de prefijos y sufijos en la subcadena buscada para optimizar la b squeda. El algoritmo prepara una funci n de prefijo que determina la mayor longitud del sufijo de una subcadena que coincide con su prefijo. Esta funci n se puede usar para buscar de manera eficiente una subcadena en una cadena.
3. Algoritmo De Rabin-Karp
El algoritmo de Rabin-Karp utiliza hashing para comparar una subcadena con una cadena. Primero se calcula el hash de la subcadena buscada, luego se calcula el hash para cada subcadena de la cadena y se compara con el hash de la subcadena buscada. Si los hashes coinciden, se realiza una verificaci n adicional para excluir coincidencias falsas.
4. Algoritmo De Boyer-Moore
El algoritmo de Boyer-Moore funciona de derecha a izquierda y utiliza tablas de desplazamiento para encontrar una subcadena de manera eficiente. Se basa en dos reglas diferentes: la regla de desplazamiento a la derecha y la regla de buen sufijo. El algoritmo busca la cadena de derecha a izquierda y desplaza la subcadena buscada de acuerdo con las reglas de desplazamiento.
5. Algoritmo Boyer-Moore - Horspool
El algoritmo de Boyer-Moore-Horspool es una modificaci n del algoritmo de Boyer-Moore que utiliza una restricci n de sufijo. El algoritmo calcula la ltima aparici n de cada car cter de la subcadena buscada y desplaza la subcadena buscada por esos valores.
6. Algoritmo Aho - Corasick
El algoritmo aho-Korasik se utiliza para buscar varias muestras en una cadena a la vez. Se basa en una estructura de datos "Bor" (trie) y busca muestras en una cadena utilizando un aut mata con un n mero finito de Estados.
7. Algoritmo Ultra-Boyer-Moore
El algoritmo Ultra-Boyer-Moore es una versi n mejorada del algoritmo Boyer-Moore. Aplica varias heur sticas para buscar de manera eficiente una subcadena en una cadena, incluidas las invalidaciones, la duplicaci n y el c lculo previo de las tablas de desplazamiento.
| Algoritmo | Estimaci n del tiempo de trabajo | |
|---|---|---|
| (Brute force) | O(n*m) | O(1) |
| - - (Knuth-Morris-Pratt) | O(n+m) | O(m) |
| - (Rabin-Karp) | O(n+m) | O(1) |
| - (Boyer-Moore) | O(n+m) | O(k) |
| - - (Boyer-Moore-Horspool) | O(n+m) | O(k) |
| - (Aho-Corasick) | O(n+m+k) | O(k) |
| - - (Ultra-Boyer-Moore) | O(n+m) | O(k) |
: n es la longitud de la cadena, m es la longitud de la subcadena, k es el n mero de muestras.
Dependiendo de las caracter sticas de la tarea y los requisitos de rendimiento, puede elegir uno de los algoritmos de b squeda de subcadenas anteriores en una cadena.
M todo de b squeda de subcadenas brute-force
El m todo brute-force (o "m todo de fuerza bruta") es la forma m s simple y directa de encontrar una subcadena en una cadena utilizando el lenguaje de programaci n C.
La idea b sica del m todo es iterar sobre subcadenas y compararlas con una cadena car cter por car cter. Si la subcadena coincide con la parte de la cadena, se encuentra la primera aparici n de la subcadena. Si la subcadena no coincide con ninguna parte de la cadena, entonces no hay ocurrencias en la cadena.
Para implementar el m todo brute-force, debe seguir estos pasos::
- Inicializar dos punteros: uno apunta al car cter actual en la cadena, el otro al car cter actual en la subcadena.
- Hasta que se alcanza el final de una cadena o subcadena, comparar caracteres con los punteros actuales.
- Si los caracteres no coinciden, mueva el puntero de la cadena una posici n hacia la derecha y el puntero de la subcadena vuelva al principio.
- Si los caracteres coinciden, deslice ambos punteros hacia la derecha.
- Si, como resultado del desplazamiento, el puntero de la subcadena ha llegado al final de la cadena, se encuentra la primera aparici n de la subcadena en la cadena y se detiene la ejecuci n del algoritmo.
El siguiente c digo en lenguaje C demuestra la implementaci n del m todo Brute-force de b squeda de subcadenas:
#include
#include
int substring_search (const char* string, const char* substring) {
int string_length = strlen(cadena);
int substring_length = strlen (subcadena);
for (int i = 0; i < = longitud de cadena-longitud de subcadena; i++) {
int j;
para (j = 0; j < longitud_substring; j++) {
if (string [i + j] != subcadena [j]) {
descanso;
}
}
if (j = = longitud_substring) {
regreso i; / /
}
}
retorno -1; / /
}
int principal() {
const char * string = " fuerza bruta ";
const char* substring = "brute-force";
int index = substring_search(string, substring);
if (index != -1) {
printf ("Subcadena encontrada en la posici n: %d
", index);
} else {
printf ("Subcadena no encontrada
");
}
return 0;
}
En este ejemplo, la subcadena "Brute-force" se busca en la cadena "m todo de b squeda de subcadena brute-force". Si se encuentra una subcadena, el programa muestra la posici n de la primera aparici n de la subcadena. De lo contrario, aparece el mensaje "Subcadena no encontrada".
El m todo brute-force es f cil de implementar, pero con grandes cantidades de datos puede no funcionar de manera eficiente. Existen algoritmos de b squeda de subcadenas m s ptimos, como el algoritmo de Knuth-Morris-Pratt y el algoritmo de Boyer-Moore.
M todo de b squeda de subcadenas de Knuth-Morris-Pratt
El m todo Knuth-Morris-Pratt (algoritmo KMP) es uno de los algoritmos efectivos para encontrar una subcadena en una cadena. Es notablemente superior a los m todos de b squeda simples, como el m todo de "fuerza bruta", basado en la comparaci n secuencial de cada personaje.
El principio de funcionamiento del algoritmo KMP es utilizar una tabla de turnos previamente preparada. Esta tabla permite que el algoritmo omita algunos caracteres al comparar una subcadena con la cadena original, lo que acelera el proceso de b squeda.
Pasos b sicos del algoritmo KMP:
- Hacemos una tabla de turnos para una subcadena dada. Esta tabla determina la cantidad de caracteres que podemos omitir cuando los caracteres no coinciden.
- Ejecutamos un bucle sobre los caracteres de la cadena original y la subcadena.
- Si los s mbolos no coinciden, miramos la tabla de turnos y nos movemos a la derecha en el n mero especificado de posiciones.
- Repita los pasos 2-3 hasta que encuentre todas las apariciones de la subcadena en la cadena.
El algoritmo KMP tiene una complejidad lineal de O (n+m), donde n es la longitud de la cadena original, m es la longitud de la subcadena. Por lo tanto, es muy eficiente para encontrar subcadenas en cadenas grandes.
Ejemplo de uso del algoritmo KMP:
| Cadena original | Subcadena | Resultado |
|---|---|---|
| abvgdabvgdabvgd | abvgd | 3 ocurrencias |
| abcdefgabcdefgabcdefg | abc | 3 ocurrencias |
| abcdefgabcdefgabcdefg | xyz | 0 ocurrencias |
El algoritmo KMP es una herramienta importante en el campo de los algoritmos de b squeda de subcadenas y se usa ampliamente en diversas aplicaciones, como procesamiento de textos, b squeda de archivos, compilaci n de programas, etc.
M todo de b squeda de subcadenas de Boyer-Moore
El m todo de Boyer-Moore es uno de los algoritmos de b squeda de subcadenas m s eficientes en una cadena. Fue dise ado en 1977 por Robert Boyer y J. R. R. Tolkien. Strouts Thompson.
La idea b sica del algoritmo de Boyer-Moore es que la b squeda de subcadenas ya no comienza con el primer car cter de la cadena, sino con el ltimo. Esto hace que sea posible omitir un cierto n mero de caracteres al comparar.
El algoritmo de Boyer-Moore consta de dos fases: preprocesamiento y b squeda. En la fase de preprocesamiento, se construye una tabla de desplazamiento en la que se determina el desplazamiento m ximo para cada car cter de cadena que se omitir en caso de no coincidencia.
En la segunda fase, cuando se busca una subcadena, se comparan los caracteres de derecha a izquierda. Si los caracteres que se comparan no coinciden, se desplaza un cierto n mero de posiciones hacia la derecha, que se define en la tabla de desplazamientos.
El algoritmo de Boyer-Moore es altamente eficiente, especialmente si la subcadena deseada tiene m s de 2 caracteres de longitud. Su complejidad es O (N/M), donde N es la longitud de la cadena original, M es la longitud de la subcadena buscada.
Ventajas del m todo de b squeda de subcadenas Boyer-Moore:
- Alta velocidad de b squeda en cadenas grandes;
- Eficiencia en la b squeda de subcadenas de gran longitud;
- La capacidad de omitir caracteres al comparar, lo que aumenta la velocidad de b squeda.
Sin embargo, el algoritmo tiene algunas desventajas:
- Ineficiente en la b squeda de subcadenas cortas;
- Requiere memoria adicional para almacenar la tabla de desplazamiento;
- La complejidad del algoritmo puede ser alta con algunos datos distorsionados.
A pesar de algunos inconvenientes, el algoritmo de Boyer-Moore es ampliamente aceptado y se usa en muchas aplicaciones y sistemas modernos para encontrar subcadenas de manera eficiente.
Ejemplos de c digo de b squeda de subcadenas en una cadena en C
A continuaci n se presentan algunos ejemplos de c digo que le permiten buscar subcadenas en una cadena en el lenguaje de programaci n C. Todos los ejemplos se presentan en la sintaxis C est ndar y no utilizan bibliotecas de terceros.
1. Ejemplo de uso de la funci n strstr()
La funci n strstr() se utiliza para buscar la primera aparici n de una subcadena en una cadena. Toma dos argumentos: un puntero a la cadena original y un puntero a una subcadena, y devuelve un puntero a la primera aparici n de una subcadena en una cadena o NULL si no se encuentra una subcadena.
#include #include
int main() {
char str [] = "cadena De ejemplo para buscar";
char substr [] ="cadenas";
char *ptr = strstr(str, substr);
if (ptr != NULL) {
printf ("Subcadena encontrada: %s
", ptr);
} else {
printf ("Subcadena no encontrada
");
}
return 0;
}
2. Ejemplo de uso de un bucle para buscar una subcadena
Otro enfoque para resolver el problema de encontrar una subcadena en una cadena es usar un bucle con una comparaci n de caracteres secuencial. En este ejemplo, repasamos cada car cter de la cadena y lo comparamos con el primer car cter de la subcadena. Si los caracteres coinciden, verificamos si el resto de los caracteres de la subcadena coinciden con los caracteres de la cadena.
#include #include
int searchSubstring(const char *str, const char *substr) {
int strLen = strlen(str);
int substrLen = strlen(substr);
for (int i = 0; i <= strLen - substrLen; i++) {
int j;
for (j = 0; j < substrLen; j++) {
if (str[i + j] != substr[j]) {
break;
}
}
if (j == substrLen) {
return i;
}
}
return -1;
}
int main() {
char str[] = " ";
char substr[] = " ";
int result = searchSubstring(str, substr);
if (result != -1) {
printf(" %d
", result);
} else {
printf("
");
}
return 0;
}
3. strcasestr()
La funci n strcasestr () busca una subcadena en una cadena sin distinguir entre may sculas y min sculas. Funciona de manera similar a la funci n strstr(), pero no distingue entre may sculas y min sculas. La funci n strcasestr () devuelve un puntero a la primera aparici n que no distingue entre may sculas y min sculas o NULL si no se encuentra una subcadena.
#include #include
int main() {
char str [] = "cadena De ejemplo para buscar";
char substr [] ="Cadenas";
char *ptr = strcasestr(str, substr);
if (ptr != NULL) {
printf ("Subcadena encontrada: %s
", ptr);
} else {
printf ("Subcadena no encontrada
");
}
return 0;
}
Estos son solo algunos ejemplos de c digo que demuestran c mo se puede buscar una subcadena en una cadena en el lenguaje de programaci n C. Es posible que desee ajustar los ejemplos a sus necesidades espec ficas o utilizar otras funciones y t cnicas para resolver este problema.
Comparaci n y selecci n del algoritmo ptimo de b squeda de subcadenas en C
Encontrar una subcadena en una cadena es una de las tareas principales cuando se trabaja con datos de texto. En el lenguaje de programaci n C, hay varios algoritmos que se pueden usar para encontrar una subcadena. Considere los principales y haga una comparaci n de su rendimiento.
1. B squeda lineal
La b squeda lineal es el algoritmo de b squeda de subcadenas m s simple. Realiza una comparaci n secuencial de cada car cter de cadena con los caracteres de subcadena. Si se encuentra una coincidencia, se verifica el siguiente car cter. Si la subcadena coincide completamente con el fragmento de cadena actual, el algoritmo devuelve el ndice de ese fragmento.
Ventajas:
- Facilidad de implementaci n
- Funciona correctamente para cualquier tipo de cadena
Deficiencias:
- Ineficiente para cadenas largas, ya que requiere una comparaci n de caracteres en cada posici n de cadena
2. Algoritmo de Knuth-Morris-Pratt (CMP)
El algoritmo de Knuth-Morris-Pratt (CMP) utiliza informaci n adicional sobre los prefijos de subcadenas para acelerar la b squeda. Construye una funci n de prefijo que le permite determinar cu nto se puede mover una subcadena cuando los caracteres no coinciden.
Ventajas:
- Eficiente para encontrar subcadenas en cadenas largas
- Complejidad del algoritmo: O (n + m), donde n es la longitud de la cadena, m es la longitud de la subcadena
Deficiencias:
- Requiere la construcci n de una funci n de prefijo, lo que agrega costos adicionales de memoria y tiempo
3. Algoritmo De Boyer-Moore
El algoritmo de Boyer-Moore se basa en el proceso de comparaci n de caracteres de derecha a izquierda. Utiliza una tabla de desplazamiento que indica cu ntas posiciones puede mover una subcadena en caso de que los caracteres no coincidan.
Ventajas:
- Efectivo para casos en los que una subcadena tiene muchos caracteres id nticos
- Complejidad del algoritmo: O (n + m), donde n es la longitud de la cadena, m es la longitud de la subcadena
Deficiencias:
- Se necesita memoria adicional para almacenar la tabla de desplazamiento
4. Algoritmo De Rabin-Karp
El algoritmo Rabin-Karp utiliza hashing para encontrar una subcadena. Calcula el valor hash de una subcadena y lo compara con los valores hash de los fragmentos de cadena. Si los valores hash coinciden, se realiza una comprobaci n adicional de la coincidencia completa.
Ventajas:
- Eficiente para encontrar varias subcadenas en una sola l nea
- Complejidad del algoritmo: O (n + m), donde n es la longitud de la cadena, m es la longitud de la subcadena
Deficiencias:
- Puede producir colisiones al calcular valores hash
- Se necesita memoria adicional para almacenar valores hash
5. rbol de sufijos
Un rbol de sufijos es una estructura de datos construida sobre la base de todos los sufijos de una cadena. Le permite buscar subcadenas de manera eficiente, encontrar todas las ocurrencias de subcadenas y realizar otras operaciones.
Ventajas:
- Eficiente para encontrar diferentes tipos de subcadenas
- Complejidad del algoritmo: O (n), donde n es la longitud de la cadena
Deficiencias:
- Requiere tiempo y memoria adicionales para construir un rbol de sufijos
| Algoritmo | Ventajas | Deficiencias |
|---|---|---|
| B squeda lineal | Facilidad de implementaci n | Ineficiente para cadenas largas |
| Algoritmo De Knuth-Morris-Pratt | Eficiente para encontrar subcadenas en cadenas largas | Requiere la construcci n de una funci n de prefijo |
| Algoritmo De Boyer-Moore | Efectivo para casos en los que una subcadena tiene muchos caracteres id nticos | Se necesita memoria adicional para almacenar la tabla de desplazamiento |
| Algoritmo De Rabin-Karp | Eficiente para encontrar varias subcadenas en una sola l nea | Puede producir colisiones al calcular valores hash |
| rbol de sufijos | Eficiente para encontrar diferentes tipos de subcadenas | Requiere tiempo y memoria adicionales para construir |
En Resumen, la elecci n del algoritmo ptimo para buscar subcadenas en C depende del problema espec fico y las caracter sticas de los datos de entrada. Si la cadena es corta y la subcadena es peque a, puede utilizar una b squeda lineal simple. Si la longitud de las cadenas es grande, vale la pena considerar los algoritmos KMP, Boyer-Moore, Rabin-Karp o usar un rbol de sufijos en el caso de tareas complejas de b squeda y procesamiento de subcadenas.
Pregunta-respuesta
C mo puedo encontrar una subcadena en una cadena usando C?
En el lenguaje C, hay varias formas de encontrar una subcadena en una cadena. Una de las formas m s simples y comunes es usar la funci n strstr(). Esta funci n toma dos filas como par metros y devuelve un puntero a la primera aparici n de la segunda fila en la primera fila. Si no se encuentra una subcadena, la funci n devuelve NULL. Ejemplo de uso de la funci n:
C mo encuentro todas las apariciones de subcadenas en una cadena en C?
Para encontrar todas las ocurrencias de una subcadena en una cadena en C, puede usar un bucle y la funci n strstr(). Comenzando desde el comienzo de la cadena, la funci n buscar una subcadena en la cadena con un bucle, escribiendo cada vez que encuentre una aparici n en una matriz o lista especial. C digo de ejemplo:
C mo encontrar una subcadena en una cadena, ignorando may sculas y min sculas en C?
Para encontrar una subcadena en una cadena, ignorando las may sculas y min sculas en C, puede usar la funci n strcasestr (). Esta funci n funciona de manera similar a la funci n strstr (), pero ignora las may sculas y min sculas al comparar cadenas. Ejemplo de uso de la funci n:
C mo encuentro el ndice de la primera aparici n de una subcadena en una cadena en C?
Para encontrar el ndice de la primera aparici n de una subcadena en una cadena en C, puede usar la funci n strstr () en combinaci n con la funci n strlen (). Despu s de llamar a la funci n strstr (), calculamos la diferencia del puntero a la subcadena y el comienzo de la cadena para obtener el ndice de la primera aparici n. C digo de ejemplo: