Labb 3

Läs igenom labbinstruktionerna innan ni börjar.

Tips: I speciellt C++ men även Java är det ganska praktiskt att använda iteratorer för att representera vektorer/mängder/etc. För mer detaljer se Labb 1.

Strängar och strängmatchning

Uppgift 3.1: Strängsökning (1p)

Implementera en funktion med vilken man kan hitta alla förekomster av en sträng pattern i en annan sträng text.

Förslag till API:
position[] find(string pattern, string text)

Rekommenderad tidskomplexitet: O(text + pattern).

Problem-id hos Kattis: stringmatching.

Ett bra testfall att tänka på om er kod är för långsam, är text = aaa...a (200000 tecken), pattern = aaaa...a (100000 tecken). Alla index från 0 till 100000 är då matchande positioner. Prova även att göra detta testfall dubbelt så stort (dvs dubblera text och pattern). Er lösning borde bara ta ca dubbel så lång tid på detta testfall (emedan en kvadratisk lösning skulle ta fyra gånger så lång tid).

Bonus (1p): Implementera en funktion som hittar alla förekomster av flera strängar pattern[] i en annan sträng text.

Förslag till API:
position[][] find(string pattern[], string text)

Rekommenderad tidskomplexitet: O(text + pattern[] + k), där k är det totala antalet matchningar av alla mönster.

Problem-id hos Kattis: stringmultimatching.

Obs! En lösning på bonus-uppgiften utgör även en lösning på den enklare uppgiften (eftersom k högst är textlängden om vi bara har ett mönster).

Uppgift 3.2: Suffixsortering (2p)

Ett suffix är en del av en sträng som utgör slutet av strängen. Strängen "popup" har 5 suffix: "p", "up", "pup", "opup", och slutligen "popup". Ett suffix kan betraktas som en position i strängen, som anger vart suffixet börjar.

Implementera en datatyp som sorterar en strängs suffix i lexikografisk ordning. Datatypen ska ha följande operationer:

constructor(string s) - skapar ett suffixobjekt från en sträng.
position getSuffix(i) - returnerar det i:te minsta suffixet.

Sorterar vi suffixen från strängen popup får vi: "opup", "p", "popup", "pup", "up". Om vi konstruerar ett suffixobjekt från "popup" ska vi alltså få: getSuffix(0) = 1, getSuffix(1) = 4, getSuffix(2) = 0, getSuffix(3) = 2, getSuffix(4) = 3.

Rekommenderad tidskomplexitet: O(s log s) för konstruktorn (obs! tänk på att jämförelser av strängar tar tid!), och konstant tid för getSuffix.

Problem-id hos Kattis: suffixsorting.

Ett bra testfall att tänka på om er kod är för långsam, är s = <W><W>, där W är en 50000 tecken lång slumpsträng.

Talteori

Uppgift 3.3 Rationella tal (1p)

Implementera en klass för rationella tal. Klassen ska åtminstone ha stöd för:

Vanliga aritmetiska operationer: addition, subtraktion, multiplikation, division.
Jämförelser.
Inläsning och utskrift

Klassen blir mer användbar om man kan välja heltalstyp för täljare och nämnare med hjälp av templates/generics, men det är inte ett krav att implementera detta.

Ett tips är att se till att lagra de rationella talen i en normaliserad form.

Problem-id hos Kattis: rationalarithmetic.

Uppgift 3.4: Implementera modulär aritmetik (1p)

Implementera modulär aritmetik, d.v.s. addition, subtraktion, multiplikation och division mod n. Det är inte tillåtet att använda färdiga paket eller klasser, exempelvis java.math.BigInteger som tillhandahåller en färdig implementation.

Tänk på att %-operatorn inte beter sig som man vill för negativa tal.

Problem-id hos Kattis: modulararithmetic.

Uppgift 3.5: Kinesiska restsatsen

Lösningarna i detta avsnitt blir mer användbara om man kan välja heltalstyp med hjälp av templates/generics, men det är inte ett krav att implementera detta.

Uppgift 3.5.1: Relativt prima moduli (1p)

Implementera en funktion som löser ekvationssystemet

x = a (mod n)
x = b (mod m)

där m och n är relativt prima. Lösaren ska returnera den unika lösning x som uppfyller 0 ≤ x < n · m.

Problem-id hos Kattis: chineseremainder.

Uppgift 3.5.2: Moduli med gemensamma faktorer (1p)

Implementera en funktion som löser ekvationssystemet ovan även när m och n inte nödvändigtvis är relativt prima. Observera att det i detta fall kan vara så att det saknas en lösning; detta ska hanteras.

Det x som hittas ska uppfylla 0 ≤ x < n · m / gcd(m,n).

Problem-id hos Kattis: generalchineseremainder.

Uppgift 3.6: Implementera primtalssållning (1p)

Implementera Erathostenes såll för att hitta alla primtal upp till en gräns n. Sållet kan t.ex. implementeras som en klass där konstruktorn tar n som parameter, och som sedan i konstant tid kan svara på frågor om huruvida ett tal mellan 0 och n är ett primtal eller inte.

Obs, er implementation måste vara både minnes- och tidseffektiv!

Problem-id hos Kattis: primesieve.