Thread starten zwei Subs - Eingabe / Ausgabe (4 answers)
Opened by Mara at 2011-12-29 11:45

Mara
 2011-12-29 11:45
#155159 #155159
User since
2011-12-29
3 Artikel
BenutzerIn
[default_avatar]
Huhu, ich versuch mich grad in Algorithmen, die Anstelle von bloßer Theorie einmal zu implementieren und dabei einen Schritt weiter zugehen, als nur kleine Miniprogramme in Perl zu schreiben die mit Fakutäten oder Mittelwerte berechnen.

Als Übung wollte ich KMP implementieren - dazu habe ich mir erstmal überlegt von der Theorie auszugehen, auf die der Algo basiert und hab, zwei Subs gemacht, die einmal das Präfix berechnen für das Muster und dann eine zweite Sub, in dem dann der Schritt passiert, wo Text und Muster geprüft werden soll, um so ein Match oder Mismatch zu erhalten.

Das war meine Überlegung, die hab ich soweit in 2 Subs implementiert, doch jetzt komm ich in dem Schritt - wie rufe ich die beiden auf und bringe das Ganze zum laufen nicht mehr weiter. Hier scheitert ich grad an mir selber. Denn ich weiß nicht wie ich dem Programm verklickern soll, das Ganze zu starten, sprich es scheitert grad bei dem Punkt:

Einlesen des Musters und des Textes, die unterschiedlich groß sein können und dann durch die Subs bearbeitet werden sollen. Und am Ende der Ausgabe.

Ich hab das was.. ich bisher gemacht hab mal eingefügt, wäre lieb, wenn mir jemand erklären könnte, wie man die Sache zum laufen kriegt und ob die Subs so stimmen. :(

Code (perl): (dl )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

#!/usr/bin/perl
use strict;
use warnings;
use interger;


# Allgemein: 
# w /P  = Wort oder Muster (Pattern)
# i = Anfangposition des Suchwortes s im Text t
# j = Position im Suchwort (Länge des Präfixes)
# t  =Text
# n  = Länge des Textes
# s = Suchtwort
# m = Länge des Suchwortes
# s = Suchwort
# m= Länge des Suchwortes 



#        Berechnung der Präfix                                           

sub ermorde_Knuth_next{              
        my($P)=@_;                        # das Muster

        my ($m;$i,$j)=(lenght $P,0,-1);   
        my @next;                         # Array 


        for ($next[0] = -1; $i < $m; ) {
        while ( $j > -1 &&
                substr( $P, $i, 1 ) ne substr( $P, $j, 1 ) ) {
            $j = $next[ $j ];
        }
        $i++;
        $j++;
        $next[ $i ] =
            substr( $P, $j, 1 ) eq substr( $P, $i, 1 ) ?
                $next[ $j ] : $j;
     }
        return ($m,@net);     # Länge des Musters und der Prefix Funktion
}


                                                        #Matcher                                                

        sub ermorde_Knuth  {         
         my ( $T, $P ) = @_;            # Text und Muster.
    
    my $m = ermorde_Knuth_next( $P );   
    my ( $n, $i, $j ) = ( length($T), 0, 0 );
    my @next;
        
        while ( $i < $n ) {
          while ( $j > -1 &&
                substr( $P, $j, 1 ) ne substr( $T, $i, 1 ) ) {
            $j = $next[ $j ];
        }
        $i++;
        $j++;
        return $i - $j if $j >= $m; # Match - Hurra wir haben einen Treffer.
    }
    return -1; # Mismatch - Shit - daneben getroffen.
}

Last edited: 2011-12-29 11:51:30 +0100 (CET)

View full thread starten zwei Subs - Eingabe / Ausgabe