Escriba su propio strlen() para una string larga rellenada con ‘\\0’s

Dada una gran array de caracteres que representa una string tal que todos los caracteres finales que no son strings se rellenan con ‘\0’ al final, es decir, todos los caracteres iniciales son caracteres de string, todos los finales son ‘\0’ y no caracteres basura. Escribe una función eficiente para encontrar la longitud de tal string.

Ejemplos:

Input: str[] = {'g', 'e', 'e', 'k', '\0', '\0', '\0', '\0', '\0', '\0'}
       n = 10  // Total no. of characters including \0's
Output: Length of string is 4     

Input: str[] = {'g', 'e', 'e', 'k', 's', 'q', 'u', 'i', 'z', '\0', '\0',
                  '\0', '\0', '\0', '\0', '\0'}
        n = 15
Output: Length of string is 9

Una solución simple es ir como la función strlen normal donde seguimos leyendo caracteres hasta que lleguemos a ‘\0’. La complejidad temporal de la corriente estándar es O(n).

Dado que todos los caracteres finales son ‘\0’, podemos usar la búsqueda binaria .
Al comparar dos elementos del medio con ‘\0’, podemos decidir si necesitamos repetir para la mitad izquierda o la mitad derecha.
SI uno de ellos es \0, entonces encontramos la primera ocurrencia.
De lo contrario, si ambos elementos son ‘\0’, entonces debemos movernos a la mitad izquierda.
De lo contrario (cuando ninguno de los elementos intermedios es \0), debemos movernos a la mitad derecha.

A continuación se muestra la implementación en C de la idea anterior.

// A Binary Search based implementation of strlen when all non-string
// characters are \0
#include <stdio.h>
  
/* if \0 is present in str[] then returns the index of FIRST occurrence
   of \0 in str[low..high], otherwise returns -1 */
int firstZero(char str[], int low, int high)
{
    if (high >= low)
    {
        // Check if mid element is first '\0'
        int mid = low + (high - low)/2;
        if (( mid == 0 || str[mid-1] != '\0') && str[mid] == '\0')
            return mid;
  
        if (str[mid] != '\0')  // If mid element is not '\0'
            return firstZero(str, (mid + 1), high);
        else  // If mid element is '\0', but not first '\0'
            return firstZero(str, low, (mid -1));
    }
    return -1;
}
  
// This function mainly calls firstZero to find length.
int myStrlen(char str[], int n)
{
    // Find index of first zero in given stray
    int first = firstZero(str, 0, n-1);
  
    // If '\0' is not present at all, return n
    if (first == -1)
        return n;
  
    return first;
}
  
/* Driver program to check above functions */
int main()
{
    char str[] =  {'g', 'e', 'e', 'k', 's', 'q', 'u', 'i', 'z', '\0', '\0',
                  '\0', '\0', '\0', '\0', '\0'};
    int n = sizeof(str)/sizeof(str[0]);
    printf("Length of string is %d", myStrlen(str, n));
    return 0;
}

Producción:

Length of string is 9

La idea es similar a las siguientes publicaciones. Realizamos una búsqueda binaria para la primera aparición de ‘\0’.
Encuentra el número de ceros
Cuenta el número de ocurrencias en una array ordenada

La complejidad de tiempo de la solución anterior es O (Logn) y el paradigma de algoritmo utilizado es Divide and Conquer .

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.