Cosa c'è di sbagliato in questo algoritmo di corrispondenza della sottostringa? [chiuso]

1

In una recente intervista mi è stato chiesto di scrivere un algoritmo che:

Data una stringa text e stringa subtext , trova le posizioni iniziali dei caratteri di ogni sottotesto trovato all'interno del testo.

"hey hi how are you hi" = 5, 20

Mi è stato vietato utilizzare qualsiasi funzione System.String ( Substring , IndexOf ecc.)

Ho scritto questo in C #:

IEnumerable<int> CalculateSubtextPositions(string text, string subtext)
{
    var charIndexToMatch = 0;
    for (int i = 0; i < text.Length; i++)
    {
        if (text[i] != subtext[charIndexToMatch])
            charIndexToMatch = 0;

        if (text[i] == subtext[charIndexToMatch])
        {
            charIndexToMatch++;
            if (charIndexToMatch == subtext.Length)
            {
                yield return i - charIndexToMatch + 2;
                charIndexToMatch = 0;
            }
        }
    }
}

Che è stato descritto come "deludente". Potrebbe essere che mi sia sfuggito qualcosa, ma non riesco a vedere cosa c'è di enormemente sbagliato in quanto sopra. Funziona, è efficiente e ragionevolmente facile da leggere rispetto a molti approcci (almeno a mio parere, per favore correggimi se sbaglio).

Le persone sarebbero in grado di suggerire dove avrei potuto incasinare? Potrebbe essere stato perché mi è stato chiesto di rendere il codice "riutilizzabile", ma non sono sicuro di quanto possa essere applicato quando ti viene chiesto di scrivere un algoritmo.

Si prega di criticare! :)

    
posta FBryant87 13.01.2016 - 20:04
fonte

1 risposta

8

Il tuo codice non è abbastanza corretto.

Quando rilevi un errore di corrispondenza, reimpostare il contatore delle partite su 0 è troppo aggressivo; come ha sottolineato Kevin, questo può perdere partite valide se il testo è costruito in modo fuorviante. Devi reimpostare su l'ultima posizione iniziale di corrispondenza globale possibile e non è facile. In un'intervista, preferirei invece optare per l'ovvia soluzione a doppio ciclo.

    
risposta data 13.01.2016 - 20:31
fonte

Leggi altre domande sui tag