Računalništvo (FMF)/Vaje/2. kolokvij 2006-2007/Rešitev 3. naloge

Iz MaFiRaWiki

3. NALOGA

Clear[Ujemanje]
Ujemanje::usage =
"Funkcija Ujemanje[S,V,s,v] vrne True, če se del niza S od položaja s naprej ujema z delom vzorca V od položaja v naprej, sicer vrne False.";

V vzorcu V lahko nastopata še posebna simbola *, ki se lahko ujema s poljubnim zaporedjem nič ali več znakov v nizu S, in ?, ki se lahko ujema s poljubnim posamičnim znakom v nizu S.

Iščemo Ujemanje[S, V, 1, 1], ki nam pove ali se niz S ujema z vzorcem V.

1. Prišli smo do konca vzorca V. Če smo prišli tudi do konca niza S vrnemo True, sicer False.

Ujemanje[S_String, V_String, s_Integer, v_Integer]/;v > StringLength[V]:=Ujemanje[S, V, s, v] /; v > StringLength[V] = s > StringLength[S]

2. V vzorcu V naletimo na "*".

Ujemanje[S_String, V_String, s_Integer, v_Integer]/;StringTake[V, {v}]== "*":=Ujemanje[S, V, s, v] /; StringTake[V, {v}]=="*" =  Module[{ss, neres},
     ss = s - 1;
     neres = False;
     While[Not[neres] && (ss ≤ StringLength[S]),
       ss = ss + 1;
       neres = Ujemanje[S, V, ss, v + 1]
       ];
     Return[neres]
     ]

Poskusimo z "*" pokriti 0, 1, 2, ... znakov niza S in zato preverimo vse možnosti. Če ena od možnosti vrne True, se neres nastavi na True, zanka se prekine in vrnemo True. Če pa v nobeni od možnosti ne dobimo True, enkrat pridemo čez cel niz S in zato se zanka prekine. Nato vrnemo False (neres je bil namreč pred zanko nastavljen na False in se v zanki ni nikoli popravil).

3. Če se znaka na položajih s v nizu S in v v vzorcu V ujemata ali če v vzorcu V naletimo na "?", se niz in vzorec doslej ujemata in zato se lahko pomaknemo za eno mesto naprej.

Ujemanje[S_String, V_String, s_Integer, v_Integer] /; s ≤ StringLength[S] && ((StringTake[V, {v}] == "?") || (StringTake[V, {v}] == StringTake[S, {s}])):= Ujemanje[S, V, s, v] /; s ≤ StringLength[S] && ((StringTake[V, {v}] == "?") || (StringTake[V, {v}] == StringTake[S, {s}])) = Ujemanje[S, V, s + 1, v + 1]

4. Nobena od dopustnih možnosti se ne zgodi, torej vrnemo False.

Ujemanje[S_String, V_String, s_Integer, v_Integer] := Ujemanje[S, V, s, v] = 
   False

Primeri:

Clear[niz, vzorec1]
niz = "abcde";
vzorec1 = "ab*e";
Ujemanje[niz, vzorec1, 1, 1]
True
Osebna orodja