122 lines
4.5 KiB
Haskell
122 lines
4.5 KiB
Haskell
module Angabe1 where
|
|
|
|
import Data.List
|
|
|
|
{- 1. Vervollstaendigen Sie gemaess Angabentext!
|
|
2. Vervollständigen Sie auch die vorgegebenen Kommentaranfänge!
|
|
3. Loeschen Sie keine Deklarationen aus diesem Rahmenprogramm, auch nicht die Modulanweisug!
|
|
4. Achten Sie darauf, dass `Gruppe' Leserechte fuer Ihre Abgabedatei hat!
|
|
-}
|
|
|
|
|
|
type Nat0 = Int
|
|
type Zeichenreihe = String
|
|
type Teilzeichenreihe = String
|
|
type IstTeilzeichenreihe = Bool
|
|
type Zerlegungszeuge = (Zeichenreihe,Zeichenreihe,Zeichenreihe)
|
|
type Zerlegungszeugen = [Zerlegungszeuge]
|
|
|
|
|
|
-- Aufgabe A.1
|
|
{-
|
|
Solution:
|
|
- if both strings are the same, True
|
|
- if the second string is empty, True
|
|
- if the second string is longer than the first, False
|
|
- otherwise, compare the first characters of both strings and call the function recursively again.
|
|
If the second string is contained in the first string, it will get equal to [] eventually and the function will return True.
|
|
If it is not, the first string will get smaller than the second eventually and the function will return False
|
|
-}
|
|
|
|
ist_tzr :: Zeichenreihe -> Teilzeichenreihe -> IstTeilzeichenreihe
|
|
|
|
ist_tzr z t
|
|
| t == z = True
|
|
| t == [] = True
|
|
| length t > length z = False
|
|
| otherwise =
|
|
if head z == head t then
|
|
ist_tzr (tail z) (tail t)
|
|
else
|
|
ist_tzr (tail z) t
|
|
|
|
-- Aufgabe A.2
|
|
{-
|
|
Solution:
|
|
- the base cases are as follows:
|
|
- both strings are empty, return a triple with empty strings
|
|
- the second string is empty, return a triple with empty strings as first two elements and the whole first string as a third.
|
|
The problem description states that the split doesn't matter, so we take this because it is easy and cheap to do :)
|
|
- the second string is not a subset of the first string, return the "error triple"
|
|
- for handling the other cases:
|
|
- we find the position of the last subset string in the first string
|
|
- we take all of the characters until this position - this is the first element of the triple
|
|
- we then take all of the characters after this position summed with the length of the second string - this is the third element of the triple
|
|
-}
|
|
|
|
tzr_zeuge :: Zeichenreihe -> Teilzeichenreihe -> Zerlegungszeuge
|
|
tzr_zeuge [] [] = ("", "", "")
|
|
tzr_zeuge z [] = ("", "", z)
|
|
tzr_zeuge z t
|
|
| not (ist_tzr z t) = ("", t ++ t, "")
|
|
| otherwise =
|
|
let pos = (find_tzr_position z t 0) - 1
|
|
pre = take pos z
|
|
suf = drop (pos + (length t)) z
|
|
in (pre, t, suf)
|
|
|
|
-- find the index of the last occurrence of t in z
|
|
find_tzr_position :: Zeichenreihe -> Teilzeichenreihe -> Nat0 -> Nat0
|
|
find_tzr_position (z:zs) t n
|
|
| not (ist_tzr (z:zs) t) = n
|
|
| otherwise = find_tzr_position zs t (n + 1)
|
|
|
|
-- Aufgabe A.3
|
|
{- Solution:
|
|
- the base cases are as follows:
|
|
- both strings are empty, return an empty array
|
|
- the second string is not a substring of the first, return an empty array
|
|
- for handling the other cases:
|
|
- find a possible split and add it to the results array
|
|
-}
|
|
|
|
tzr_zeugen :: Zeichenreihe -> Teilzeichenreihe -> Zerlegungszeugen
|
|
tzr_zeugen [] [] = []
|
|
tzr_zeugen z t
|
|
| not (ist_tzr z t) = []
|
|
| otherwise = get_all_substring_variants z t []
|
|
|
|
get_all_substring_variants :: Zeichenreihe -> Teilzeichenreihe -> Zerlegungszeugen -> Zerlegungszeugen
|
|
get_all_substring_variants z t r
|
|
| not (ist_tzr z t) = r
|
|
| otherwise =
|
|
let
|
|
pos = (find_tzr_position z t 0) - 1
|
|
new_res = r ++ [(tzr_zeuge z t)]
|
|
in
|
|
get_all_substring_variants (take pos z) t new_res
|
|
|
|
|
|
-- Aufgabe A.4
|
|
{-
|
|
Solution:
|
|
- we handle the case when the second string is empty - the result is always the length of the first string + 1
|
|
- if the second string is not a substring of the first one, return 0 as a result
|
|
- otherwise, count how many times the second string occurs in the first string by counting how many times the first string can be "cut" on the position of the second string
|
|
-}
|
|
|
|
wieOft :: Zeichenreihe -> Teilzeichenreihe -> Nat0
|
|
wieOft z [] = (length z) + 1
|
|
wieOft z t
|
|
| not (ist_tzr z t) = 0
|
|
| otherwise = count_sub_string z t 0
|
|
|
|
--- find how many times a substring occurs in a string
|
|
count_sub_string :: Zeichenreihe -> Teilzeichenreihe -> Nat0 -> Nat0
|
|
count_sub_string z t n
|
|
| not (ist_tzr z t) = n
|
|
| otherwise =
|
|
let
|
|
pos = (find_tzr_position z t 0) - 1
|
|
in count_sub_string (take pos z) t (n + 1)
|