Hemtal 5

A) Skriv en KMP-automat som söker efter ordet MATEMATIK i en text. Ange också den next-vektor som definierar automaten.

B) Visa hur automaten fungerar på texten MMATEMATEMATIKIK (som lagras i en kö) genom att ange vilken följd av tillstånd som automaten genomgår under sökningen. Om ordet hittas, dvs sluttillståndet nås, avslutas sökningen. En programskiss:

s="MATEMATIK"
i=1 # starttillståndet
while i < len(s)+1 and not q.isempty():
    if i==0 or q.peek()==s[i-1]: 
        i=i+1
        q.get()
    else:
        i=next[i]

Rättningsmall

Står namnet överst till höger?

Den som gjort uppgiften ska skriva sitt namn och personnummer överst till höger på alla papper. Den som rättar ska skriva sitt namn och personnummer, samt "G" eller "IG" överst till vänster på första pappret.

Är det tydligt skrivet?

Går det att begripa? Är något otydligt? Kan man läsa allt i figuren?

Är det rätt svar?

Är det rätt svar? Svaren gås igenom på övning.