Datastructuren en algoritmen
Welke eigenschap van het Boyer-Moore-algoritme om een patroon in een tekenreeks te vinden is juist?
- AHet vergelijkt het patroon vanaf het laatste teken en gebruikt informatie, bijvoorbeeld dat het niet-overeenkomende teken van de tekst niet in het patroon voorkomt, om het patroon in één keer een flink eind op te schuiven
- BHet schuift het patroon vanaf het begin van de tekst telkens één teken op en vergelijkt elke keer alle tekens van het patroon van eerste tot laatste
- CHet sorteert zowel de tekst als het patroon en vindt het patroon daarna met binair zoeken
Antwoord en toelichting tonen
Antwoord: A. Het vergelijkt het patroon vanaf het laatste teken en gebruikt informatie, bijvoorbeeld dat het niet-overeenkomende teken van de tekst niet in het patroon voorkomt, om het patroon in één keer een flink eind op te schuiven
Het Boyer-Moore-algoritme vergelijkt het patroon vanaf het laatste teken en berekent vooraf tabellen, zodat het hele patroon bijvoorbeeld voorbij een niet-overeenkomend teken van de tekst kan worden geschoven als dat teken helemaal niet in het patroon voorkomt. Daardoor kan het in natuurlijke tekst veel tekens overslaan zonder ze te vergelijken. Bij een tekst van lengte n en een patroon van lengte m kost de naïeve methode, die telkens één teken opschuift en alles vergelijkt, in het slechtste geval O(nm). Het KMP-algoritme gebruikt ook informatie over de mismatch om op te schuiven, maar vergelijkt vanaf het begin van het patroon en garandeert ook in het slechtste geval O(n + m).