Trova modello in una stringa [chiuso]

Se mi fosse stata posta questa domanda in un'intervista, questo sarebbe stato il modo in cui avrei iniziato a capire il mio algoritmo. Nota: i primi due casi sono proprio come vorrei arrivare alla risposta finale, e in realtà non sono una risposta adatta fino al numero 3.

Vorrei iniziare con il caso facile che è dove non c'è "?" o '*'. Vorrei fare una scansione della stringa di ricerca fino a quando non ho colpito il primo carattere nella stringa del modello. A quel punto, vai al prossimo carattere nella stringa del modello e vedi se corrisponde al prossimo carattere nella stringa di ricerca. Se lo fa, continua, altrimenti torna all'inizio della stringa del modello ma mantieni la posizione corrente nella stringa di ricerca. Quando finisci i caratteri nella stringa del pattern, allora hai una corrispondenza, se esaurisci i caratteri nella stringa di ricerca, non lo fai.

Quindi passa al caso di un '?' personaggio. Fai lo stesso algoritmo di prima, tranne quando premi "?" nella stringa del modello, vai avanti e salta la posizione corrente nella stringa di ricerca e ottieni il prossimo carattere nella stringa del modello. Continua come nel caso 1.

Quindi passa al caso finale di "?" e '*' permesso. Fai lo stesso degli altri due casi, tranne quando tocchi un '*', trova immediatamente il carattere successivo dopo il '*' nella stringa del modello. Quindi scansiona la stringa di ricerca per trovare il prossimo carattere. Se lo trovi, continua con il caso 1 & 2, quando sei fuori dai personaggi del pattern hai una corrispondenza. Se si esauriscono i caratteri della stringa di ricerca, passare all'istanza successiva nella stringa di ricerca del carattere immediatamente dopo "*" nella stringa del pattern e riprovare. Se non lo hai ancora trovato, potresti aver avuto un falso allarme con la prima partita. Quindi, inizia dal punto in cui hai iniziato l'ultimo controllo delle partite e ripeti l'intero processo. Quando raggiungi la fine della stringa di ricerca, non hai una corrispondenza.

A questo punto, hai risolto il problema. La soluzione è O (n) nella maggior parte dei casi, ma il caso peggiore potrebbe essere O (n ^ 2)

Se dovessi effettivamente risolvere questo problema probabilmente avrei semplicemente trasformato il pattern in un modello di espressione regolare sostituendo * con [A-Za-z0-9]* e ? con [A-Za-z0-9] quindi usa regex per abbinare la stringa al pattern.

Per un colloquio probabilmente dovrei dare una risposta come quella di Jonathan perché immagino che sia quello che stanno cercando

Chiamerei semplicemente la funzione. fnmatch (3) (POSIX.2; su altre piattaforme dovrei solo scavare da qualche emulazione posix biblioteca). La maggior parte delle altre lingue oltre a C / C ++ ha anche questa funzione.

Se l'intervistatore non era soddisfatto di quella risposta, la conterei contro la società per decidere se loro ha fatto la recensione.

Se all'intervistatore è piaciuta la risposta, ma ha chiesto di implementarla, c'è:

• semplice variante ricorsiva (usando pseudo-codice arbitrario) (O ( mn ) peggiore):

  bool matches(string:string, pattern:string):
      if pattern[0] == '*':
          # assuming || short-circuits this order is the faster on average
          return matches(string, pattern[1:]) || matches(string[1:], pattern)
      elseif pattern[0] == '?' or pattern[0] == string[0]:
          return matches(string[1:], pattern[1:])
      else:
          return False
  

• la variante complicata che compila l'automa finito (O (n) nel tempo scambiato per una maggiore complessità spaziale per la complessità automa / temporale del preprocesso, che penso sia O ( m < sup> 2 ), ma sono troppo pigro per derivare proprio adesso).

Approccio pragmatico:

1. Converti la stringa del modello in una stringa Regex valida.
   • Sostituisci semplicemente ? con \w e * con \w* o \w+
2. Usa la regex per cercare il pattern

Ho intenzione di fare un crack a questa soluzione. Jonathan ne ha il senso generale, ma ho visto un possibile problema e mi piace la sfida di tentare una soluzione da solo.

Questa soluzione presuppone naturalmente che le espressioni regolari non siano un'opzione. Espressioni regolari esistono espressamente per corrispondere a schemi complessi come questo in modo efficiente, e sono un strong sostenitore dei programmatori che scrivono librerie modulari che fanno bene una cosa e una cosa, e tutti gli altri programmatori che usano quella libreria invece di reinventare la ruota .

La mia opinione su questo è che * crea una situazione interessante in cui un numero di soluzioni diventa possibile e non solo uno. Per verificare la stringa corrispondente per tutte queste possibilità, è necessario verificare letteralmente tutte queste possibilità. Per fare un esempio, potrei fare in modo che pattern a * bc corrisponda ad azbbc, e se si assume che b segue la z appartiene alla sezione dopo *, non si combina ciò che altrimenti sarebbe una corrispondenza. Allo stesso modo, se non si presuppone che b segue la z per appartenere alla sezione dopo *, allora non si abbina più azbc.

Quindi una versione semplificata dell'algoritmo è la seguente ( l'implementazione può essere vista qui ):

function search(matchString, pattern) {  
    var i = 0;

    // For each character in matchString and pattern
    for(; i<matchString.length && i<pattern.length; i++) {
        if(pattern[i] === '*') {
            // Star!  If pattern has been valid up to now, then
            // only one match must be valid after the *, so pass responsibility
            // to searchStar.
            var subMatchString = matchString.substring(i, matchString.length);
            var subPattern = pattern.substring(i+1, pattern.length);

            return searchStar(subMatchString, subPattern);
        } else if (pattern[i] !== '?') {
            // If it isn't * and it isn't ?, then compare characters.
            // If characters don't match, we know it isn't valid.
            if(matchString[i] !== pattern[i]) {
                return failure(matchString, pattern);
            }
        } // else if (pattern[patternIndex] === '?') {
            // Ignore '?'.. move along
        //}
    }
    if(i === pattern.length) {
        return success(matchString, pattern);  // pattern exhausted
    } else {  
        return failure(matchString, pattern);  // matchString ended with unmatched pattern
    }
}

// This function is called when star is encountered in pattern and
// pattern thus far is correct.  This applies search on remaining
// match string and returns true if even one proves true.
function searchStar(matchString, pattern) {
    while(matchString.length > 0) {  
        if(search(matchString, pattern)) {
            return true;
        }
        matchString = matchString.substring(1, matchString.length);          
    }
    return failure(matchString, pattern);
}

L'efficienza può probabilmente essere migliorata facendo piccole cose come ignorare i "*" duplicati e cose del genere, ma ho cercato di mantenerlo il più semplice possibile in modo che il lettore possa capire l'idea generale.

Spero che ti aiuti!

Ecco un'implementazione ingenua, ma testata e funzionante che utilizza la ricorsione. Penso che sia O (n ^ 3) a causa dei tre casi sull'asterik. C'è un numero decente di casi d'angolo in questo problema.

Dr. Dobbs ha una discreta recensione su questo problema: link

Sebbene uno dei commenti suggerisse l'uso di Boyer-Moore, non sembra normale che Boyer-Moore supporti i caratteri jolly. C'è un post sul blog che aggiunge i caratteri jolly alla ricerca di stringhe KMP - link

from collections import namedtuple
import string
import unittest

LITERAL_CHARS = set(string.ascii_letters + string.digits)

def simple_matcher(pattern, string):
    if pattern == "":
        if string == "":
            return True
        else:
            return False

    # We have a non-empty pattern
    else:

        if string == "":
            # If we only have * in the pattern, we can match the empty string.
            if all(p == "*" for p in pattern):
                return True
            else:
                return False

        # We have a non-empty pattern and string
        else:
            if pattern[0] in LITERAL_CHARS:
                return (pattern [0] == string [0]
                        and simple_matcher(pattern[1:], string[1:]))
            elif pattern[0] == "?":
                return simple_matcher(pattern[1:], string[1:])
            elif pattern[0] == "*":
                return (
                    # Match one char with * and keep going
                    simple_matcher(pattern[0:], string[1:])
                    or
                    # Don't use the *
                    simple_matcher(pattern[1:], string[0:])
                    or
                    # Only match one char with *
                    simple_matcher(pattern[1:], string[1:]))



Result = namedtuple('Result', ['pattern', 'string', 'expected'])

class TestSimpleMatcher(unittest.TestCase):


    def test_empty_string(self):
        results = [Result("", "", True),
                  Result("a", "", False),
                  Result("?", "", False),
                  Result("*", "", True),
                  Result("**", "", True),
                  Result("***", "", True)]
        for pattern, string, expected in results:
            self.assertEqual(simple_matcher(pattern, string), expected)

    def test_empty_pattern(self):
        results = [Result("", "", True),
                  Result("", "a", False),
                  Result("", "1", False),
                  Result("", "A", False),
                  Result("", "aaasdfasdf", False)]
        for pattern, string, expected in results:
            self.assertEqual(simple_matcher(pattern, string), expected)

    def test_literals_against_one_char_string(self):
        results = [
            Result("a", "a", True),
            Result("A", "A", True),
            Result("1", "1", True),

            Result("2", "a", False),
            Result("4", "A", False),
            Result("B", "1", False)
        ]

        for pattern, string, expected in results:
            self.assertEqual(simple_matcher(pattern, string), expected)

    def test_question_marks_against_one_char_string(self):
        results = [
            Result("?", "a", True),
            Result("?", "A", True),
            Result("?", "1", True),

            Result("??", "a", False),
            Result("??", "A", False),
            Result("??", "1", False),
        ]
        for pattern, string, expected in results:
            self.assertEqual(simple_matcher(pattern, string), expected)

    def test_asteriks_against_one_char_string(self):
        results = [
            Result("*", "a", True),
            Result("*", "A", True),
            Result("*", "1", True),
            Result("**", "a", True),
            Result("***", "a", True),
            Result("*****", "a", True),
        ]
        for pattern, string, expected in results:
            self.assertEqual(simple_matcher(pattern, string), expected)

    def test_combinations_against_one_char_string(self):
        results = [
            Result("*?", "a", True),
            Result("*A", "A", True),
            Result("*?*", "a", True),
            Result("*A*", "A", True),

            Result("*?a", "a", False),
            Result("*B", "A", False),
            Result("*??*", "a", False),
            Result("*A*?", "A", False),
        ]
        for pattern, string, expected in results:
            self.assertEqual(simple_matcher(pattern, string), expected)


    def test_combinations_against_three_char_string(self):
        results = [
            Result("*?", "aaa", True),
            Result("???", "aaa", True),
            Result("?*A", "BAA", True),
            Result("*E*", "1EF", True),
            Result("*", "123", True),
            Result("****", "123", True),

            Result("*?a*", "abc", False),
            Result("*B", "Bod", False),
            Result("????", "joe", False),
        ]
        for pattern, string, expected in results:
            self.assertEqual(simple_matcher(pattern, string), expected)

if __name__ == '__main__':
    unittest.main()