6, Πίνακες, Παράρτημα Β, ΙΕΠ, ΕΠΥ, 22ος Π.Δ.Π (2010) B’ Φάση (Θέμα Γυμνασίου) – Αναζήτηση φράσης σε συμβολοσειρά

Καθηγητής Πληροφορικής ενός Λυκείου, αντιμετώπισε ένα ξαφνικό πρόβλημα. Ο αφοσιωμένος υπολογιστής που καταγράφει τα κείμενα που εμφανίζονται στον «έξυπνο» ηλεκτρονικό πίνακα του εργαστηρίου Πληροφορικής, του «έδειξε» μπλε οθόνη! Με χρήση ειδικών εργαλείων λογισμικού ανάκτησε σε φυσικό επίπεδο (surface reading) τμήμα των αρχείων του δίσκου, χωρίς όμως τα στοιχεία χρόνου. Έτσι δυστυχώς όλες οι θέσεις που αντιστοιχούσαν στο περιεχόμενο του «έξυπνου» ηλεκτρονικού πίνακα ήταν πλήρεις με χαρακτήρες. (Τους τελευταίους που είχαν αναγραφεί στην κάθε θέση). Για την ανάκτηση των στοιχείων χρόνου, χρειάζεται να βρει τη θέση στη συμβολοσειρά που είναι εγγεγραμμένη στο δίσκο, τουλάχιστον μιας φράσης, που θυμάται ότι είχε γράψει την τελευταία φορά.

Παράδειγμα:

Στην ευρύτερη συμβολοσειρά AQKDLJKNF,IMBUBBBLE SORTDIHEWN  GLM  FR  &JSALJFLMC , η συμβολοσειρά BUBBLE SORT ξεκινά στη 13η θέση.

Πρόβλημα:

Να αναπτύξετε ένα πρόγραμμα σε Γλώσσα, το οποίο αφού εισαγάγει μια συμβολοσειρά σε έναν μονοδιάστατο Πίνακα 100 θέσεων, θα εισαγάγει μια δεύτερη συμβολοσειρά σε έναν Πίνακα 20 θέσεων και θα εμφανίζει τη θέση στον αρχικό πίνακα που αυτή ξεκινά. Αν δεν υπάρχει, θα εμφανίζει κατάλληλο μήνυμα. ΕΠΥ, 22^ος Π.Δ.Π. (2010) Β’ Φάση (Θέμα Γυμνασίου)

ΛΥΣΗ

ΠΡΟΓΡΑΜΜΑ ΑΣΚ6_ΠΑΡ_Β_ΙΕΠ_ΠΙΝ_ΑΝΑΚΤΗΣΗ_ΣΥΜΒΟΛΟΣΕΙΡΑΣ
ΣΤΑΘΕΡΕΣ
  m=50    ! ευρύτερη συμβολοσειρά
  n=10     ! φράση που αναζητείται
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ:i,j, thesi
  ΧΑΡΑΚΤΗΡΕΣ: a[m], b[n]
  ΛΟΓΙΚΕΣ: found, no_match
ΑΡΧΗ
  ΓΙΑ i  ΑΠΟ 1 ΜΕΧΡΙ m
    ΔΙΑΒΑΣΕ a[i]
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  ΓΙΑ i  ΑΠΟ 1 ΜΕΧΡΙ n
    ΔΙΑΒΑΣΕ b[i]
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  ! ξεκινώντας από κάθε επόμενο στοιχείο του α, συγκρίνω
  ! στοιχείο με στοιχείο, μέχρι το τέλος της φράσης.
  i <-- 1
  found <-- ΨΕΥΔΗΣ
  ΟΣΟ found = ΨΕΥΔΗΣ ΕΠΑΝΑΛΑΒΕ

    ! ελέγχω αν οι επόμενοι χαρακτήρες ταιριάζουν με τη φράση
    ! στο πρώτο στοιχείο που δεν ταιριάζει εγκαταλείπω
    j <-- 1
    no_match <-- ΨΕΥΔΗΣ
    ΟΣΟ no_match = ΨΕΥΔΗΣ ΚΑΙ j<=n ΕΠΑΝΑΛΑΒΕ
      ΑΝ a[i+j-1] <> b[j]  ΤΟΤΕ
        no_match <-- ΑΛΗΘΗΣ
      ΑΛΛΙΩΣ
        j <-- j+1
      ΤΕΛΟΣ_ΑΝ
      ΑΝ no_match = ΨΕΥΔΗΣ ΤΟΤΕ
        thesi <-- i
        found <-- ΑΛΗΘΗΣ
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    i <-- i+1
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΡΑΨΕ 'Θέση Αρχής', thesi

ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ