Methoden indexOf

[hugolam]

Hallo allerseits,

ich habe SChwierigkeiten diese Aufgabe zu lösen. Ich habe in versch. Foren nach Hilfestellungen gesucht und habe ca 3 Stunden versucht diese Methode zu schreiben, leider erfolglos. Ich bitte um eure Unterstützung.
Danke


AUFGABENSTELLUNG:

public static int indexOf(char[] arr, String search) {
//FILL IN!
return 0;
}


/**
* liefert den Index innerhalb des spezifizierten Arrays des ersten
* Vorkommnisses des spezifizierten Strings. Das Original-Array bleibt
* unveändert.
*
* ACHTUNG: Diese Methode soll ohne Aufruf von Methoden aus
* java.util.Arrays oder Systems.arraycopy und ohne Verwendung der
* Datentypen String, StringBuffer oder StringBuilder vervollständigt
* werden.
*
* parameter1: arr das Original-Array
* parameter2: search dieser String enthät die Zeichenfolge nach der
* gesucht werden soll.
* return: der erste Index des ersten Vorkommnisses
* der angegebenen Zeichenfolge im Array, oder -1 falls die
* Zeichenfolge gar nicht vorkommt.
*/

 

[Spewer]

Zeig doch mal deine Ansätze, vllt waren die ja garnicht schlecht.
So wird sonst niemand hier helfen ( // FILL IN )

 

[bone2]

ohne Verwendung der Datentypen String

parameter2: search dieser String enthät die Zeichenfolge nach der gesucht werden soll

wer hat sich des das ausgedacht

 

[Marco13]

Jemand der KEIN
return new String(someArray).indexOf(someOtherString);
sehen will

 

[Spacerat]

Das mit dem "habe gesucht" würde ich mir noch mal überlegen. Wenn du irgendwas gesucht hast und dabei mehr als 15 Suchanfragen abgeschickt hast waren das mehr Suchanfragen, als die Lösung Zeilen hätte (jede Wette ). Wenn man also nach der ersten nicht gleich fündig wurde, hat man irgendwas gesucht, aber nichts was einem zur Lösung führt.

 

[Pentalon]

Hi Hugolam

Zeig doch mal was Du gemacht hast.
Vielleicht denkst Du nur etwas zu kompliziert.
Dein Lehrer will einfach, dass Du verstehst, wie man so eine Methode, die man heute in JAVA benutzt, aufbaut.
Ich hab Deine Aufgabe gerade umgesetzt und sie funktioniert genauso gut wie die JAVA Methode.

Ich habe den Suchstring auch zu einem Char Feld gemacht und prüfe das ganze in 2 verschachtelten Schleifen. Alles in allem 7 Zeilen.

Ich helfe Dir gerne bei Deinem Ansatz, so wie auch sehr viele andere in diesem Forum. Aber der erste Code muss von Dir kommen.

Pentalon

 

[Bernd Hohmann]

Die Aufgabe ist aber auch echt blöde. Der schwierigste Schritt ist eine Art "normalisierung" (also wie bekomme ich entweder das char-Array in einen String oder den String in ein char-Array damit auf beiden Seiten gleiche Bedingungen herrschen).

Weil in der Vorgabe steht, dass man von den String-Funktionen fernhalten soll, kopieren wir erstmal den String in ein char-Array und geben den armen Variablen mal Namen die verständlich sind um ein Fleisskärtchen vom Dozenten zu erhalten:

public static int indexOf(char[] chHeuhaufen, String strNadel) {
   char[] chNadel = strNadel.toCharArray();

Was möchte die Vorgabe? Finde "chNadel" in "chHeuhaufen", liefere den Index zurück oder -1 wenn nix gefunden wurde. Also ein klassischer "INSTR" Algorithmus. Da kann man jetzt im Web schauen nach "StringMatching" oder "StringSearch", oder in den Source von java.lang.String schauen wie es dort läuft. Vielleicht auch Wikipedia?

Ich würde auf jedenfall erstmal den ganz naiven Ansatz bauen, den auch String#indexOf(...) nutzt.

Also eine äussere Schleife über chHeuhaufen for (i1=0;i1<chHeuhaufen.length-chNadel.length;i1++) und dann das Zeichen an chHeuhaufen[i1] mit chNadel[0] vergleichen bis es passt. Dann mit einer weiteren Schleife i2 chHeuhaufen[i1+i2] mit chNadel[i2] vergleichen - läuft diese Schleife bis zum Ende durch, wurde der chNadel gefunden und i1 wird zurückgeliefert.

Wenn man den Source von String#indexOf(..) entsprechend substituiert (Du suchst immer von Anfang bis Ende), kürzt sich da einiges heraus und Du hast eine schlanke Routine.

Bernd

 

[hüteüberhüte]

Wieso wird nie das bestens geeignete .charAt(int index) erwähnt, sondern immer erst mal versucht, umständlich aus einem String ein Array zu machen?

Abgesehen davon scheint dein Lehrer/Dozent keine Ahnung zu haben: In der Funktion darf String nicht verwendet werden, aber einer ihrer vorgegebenen Parameter ist genau ein solcher. Blöt

 

[hüteüberhüte]

Wenn du schon ewig danach gesucht hast, ohne etwas zu finden, und selbst auch keine Idee hast, dann hier von mir 'ne

Spoiler: "Musterlösung"

    public static int indexOf(char[] arr, String search) {
        a:
        for (int i = 0; i < arr.length - search.length() + 1; i++) {
            for (int j = 0; j < search.length(); j++) {
                if (arr[i + j] != search.charAt(j)) {
                    continue a;
                }
            }
            return i;
        }
        return -1;
    }

Und eine

Spoiler: Methode zum Testen

    public static void main(String[] args) {
        Random r = new Random();
        for (int i = 0; i < 10; i++) {
            StringBuilder builder = new StringBuilder();
            for (int j = 0; j < 13; j++) {
                builder.append((char) ('a' + r.nextInt('z' - 'a' + 1)));
            }
            String search = builder.substring(r.nextInt(builder.length()));
            System.out.println(builder + ", " + search + " = " + indexOf(builder.toString().toCharArray(), search));
        }
    }

yvcllkivvmrnt, rnt = 10
itdcsbvuhswsi, hswsi = 8
udnfxtjkrhnpu, u = 0
hnvivxfmtyzeh, h = 0
cpazozgbhrqil, il = 11
bncltyqysqjhg, bncltyqysqjhg = 0
kkpvxpyutgcfy, tgcfy = 8
ynlttskevrbum, nlttskevrbum = 1
gqkhhcbgktoho, bgktoho = 6
zprqnjjyxufek, zprqnjjyxufek = 0

 

[hugolam]

Danke für die Anworten!
Das nächste mal poste ich auch meine Lösungsansätze.

Zu hüteüberhüte's Lösung;
So habe ich es lange versucht und nicht geschafft.
Das mit "continue" ist sehr paraktisch das kannte ich bis jetzt nicht.
Danke nochmal fürs posten einer Lösung das hat mir sehr geholfen und hoffe dass ich jetzt für den TEst den ich diese Woche absolvieren muss bereit bin.

Hier noch eine Methode in der indexof aufgerufen wird, die ich alleine geschafft habe (falls jemand üben will ;-))

public static void verdecken(char[] arr, String s) {

while (indexOf(arr,s) >= 0) {
int ei = indexOf(arr,s);

for (int i = ei; i<s.length()+ei; i++) {

arr = '*';
}


}
}
}

/**
* Diese Prozedur sucht im spezifizierten Array nach der durch
* den String angegebenen Zeichenfolge und ersetzt jedes Zeichen
* innerhalb der Vorkommnisse im Array durch einen Stern ("*").
*
* Es besteht die Möglichkeit, dass die Zeichenfolge mehrfach vorkommt.
* Es soll jedes weitere Vorkommen der Zeichenfolge ebenfalls
* zensiert werden.
*
* arr das Original-Array
* s die zu zensierende Zeichenfolge als String
*/

 

[hüteüberhüte]

Danke nochmal fürs posten einer Lösung das hat mir sehr geholfen und hoffe dass ich jetzt für den TEst den ich diese Woche absolvieren muss bereit bin.

Aber aufpassen: Manche Profs haben eine Aversion gegen continue/break/Sprungmarken

Aber freut mich, wenn ich helfen konnte

PS: Deine Methode sieht richtig aus, aber infiniter Regress, wenn Sternchen durch Sternchen ersetzt werden

 

[Pentalon]

Hier noch meine Variante zum Vergleich:

public class Test3 {

	// Die altmodische zu Fuss-Variante
	public static int indexOf(char[] arr, String search) {
		
		if (arr.length < search.length()) return -1;
		char[] such = search.toCharArray();
		
		for(int a = 0; a<(arr.length-such.length+1); a++) {
			for(int b = 0; b<such.length; b++) {
				if (arr[a+b] != such[b]) break;
				else if (b == such.length-1) return a;  // Zeichenkette gefunden	
			}
		}
		return -1;
	}

	// Die Moderne JAVA-Variante :-)
	public static int indexOf1(char[] arr, String search) {
		return new String(arr).indexOf(search);
	}
	
	public static void main(String[] args) {
		
		char[] feld = {'d','a','s',' ','i','s','t',' ','e','i','n',' ','t','e','s','t'};
		System.out.println("Index gefunden bei "+Test3.indexOf(feld, "ein"));
		System.out.println("Index gefunden bei "+Test3.indexOf1(feld, "ein"));
	}
}

Pentalon