Labb 2: Rättstavning
Om du redovisar labben senast den 28 september får du en bonuspoäng på tentan.
På övningen den 20 september har du dessutom möjlighet att redogöra för lösningen på teoriuppgifterna nedan. Korrekt lösning av dessa ger en bonuspoäng på tentan. Sen redovisning ger ingen bonus för labb eller teoriuppgifter.
I katalogen ProblemEditeringsavståndet mellan två ord är det minimala antalet bokstavsoperationer som krävs för att transformera det ena ordet till det andra. Det finns tre tillåtna bokstavsoperationer:
alroitm -> algoitm -> algoritm visar att editeringsavståndet mellan alroitm och algoritm är högst 2. Eftersom det inte går att transformera alroitm till algoritm i en enda bokstavsoperation så är editeringsavståndet mellan orden precis 2. Ett vanligt sätt att ta fram rättstavningsförslag till ett felstavat ord är att helt enkelt returnera dom ord i ordlistan som har minst editeringsavstånd till det felstavade ordet. Programmet ska givet en ordlista och ett antal felstavade ord beräkna rättstavningsförslag på detta sätt. Specifikation Indata består av två delar. Den första delen är ordlistan,
som består av ett antal ord i utf-8-bokstavsordning, ett ord per rad.
Denna del avslutas av en rad som bara innehåller ett ' Programmet ska för varje felstavat ord skriva ut en rad bestående av det felstavade ordet följt av det minimala editeringsavståndet inom parentes följt av en lista med alla ord i ordlistan som har minimalt editeringsavstånd till det felstavade ordet. Listan ska vara i bokstavsordning och varje ord i listan ska föregås av mellanslag. Ordlistan har högst en halv miljon ord och antalet felstavade ord i indata är högst 100. Exempel på körning En ordlistefil finns i spel01$ cat /info/adk12/labb2/ordlista testord.txt | java Main labd (1) labb lagd land dabbbhud (4) anbud dabba nabbad UppgiftDet givna Javaprogrammet löser visserligen ovanstående problem, men det tar timmar att få fram svaret. Du ska effektivisera programmet så att det hittar svaret inom den tidsgräns som Kattis ger. Bra testfall att testa ditt program med finns på
Teoriuppgifterna ger uppslag om olika sätt att effektivisera programmet. Ditt optimerade program ska ha samma in- och utmatning som det givna programmet och det måste fortfarande vara Java.
Kattis känner till problemet som adkspelling TeoriuppgifterSätt dig in i hur det givna programmet fungerar och svara sedan på följande frågor.
|