Java Implementierung von "contains"

Question

Hallo,

ich versuche die "contains" Funktion von Java selber nach zu
implementieren.
Es gibt zwei Strings. Es soll überprüft werden, ob der erste String
ein Bestandteil des zweiten Strings ist.

Momentan habe ich folgendes:

public class ContainsImplementation {

public static void checkstring(String a, String b) {
for (int i = 0; i < a.length(); i++) {
if (a.charAt(i) == b.charAt(i)) {
System.out.println("True. Letter " + a.charAt(i)+ " is
the same");
} else {
System.out.println(false);
}
}

public static void main(String[] args) {
String a = "World";
String b = "Hello World!";
checkstring(a,b);

}
}

Ausgabe wäre hier:

false
false
false
True. Letter l is the same
false
da ja nur der Buchstabe 'l' gleich ist.


Mein Problem:
Momentan werden nur die Strings mit der Länge von String a
verglichen. Da ja der erste String kürzer ist, kann ich nicht mit einer
For-Schleife über b.charAt(i) iterieren, da ich sonst eine Exception
bekomme.
Es wird also nur "World" mit "Hello" verglichen.
Zudem sollen ja nicht nur einzelne Buchstaben sondern ganze
Wortteile verglichen werden.

Jemand eine Idee?

Ich weiß, dass ich noch eine weitere For-Schleife benötige aber
keine Ahnung, wie ich diese richtig implementiere.

Danke im Vorraus!

Lukas

Answer 1

Ich fang mal so an:
Du vergleichst die Buchstaben jeweils an der gleichen Position der Strings.
Richtig wäre es, das Suchwort immer weiter zu verschieben, bis man entweder einen Match gefunden hat, oder man es über die Grenzen des zu durchsuchenden Strings ('Haystack') schiebt.
Lass mich demonstrieren

World
||||| -> nicht gleich
Hello World
-------------------------------------
World
||||| -> nicht gleich
Hello World
-------------------------------------
usw....
-------------------------------------
World
||||| -> nicht gleich
Hello World
-------------------------------------

World
||||| -> gleich
Hello World

Du musst also, wie du selbst erkannt hast, eine weitere Schleife nutzen, die einen Offset zum Haystack rechnet.
also in etwa: b.charAt(i+offs)
Außerdem fehlt dir noch eine Abbruchbedingung, aber dazu später ;)

Ele

Answer 2

Ich werkel jetzt schon länger daran aber es klappt noch nicht wirklich.
Die Abfrage für:
p = "world"
t = "worldwideweb"
liefert zwar true, aber nur weil der String 'world' im zweiten String an gleicher Stelle liegt.

Die Abfrage für:
p = "swag"
t = "volkswagen"
liefert false.

Hier nochmal der abgeänderte Quellcode:

/**
* Implementation of the Java Method 'contains'
*
*/
public class ContainsImplementation {
public static char[] firstString;
public static char[] secondString;
static boolean equals = false;

/**
* Converts the String into a Char array
*
* @param string String which should be converted
* @return
*/
public static char[] convertToChar(String string) {
char[] array = new char[string.length()];
for (int i = 0; i < string.length(); i++) {
array[i] = string.charAt(i);
}
//printCharArray(array);
return array;
}


/**
* Prints out the new Char Array
*
* @param array The converted Char array
*/
public static void printCharArray(char[] array) {
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]);
}
System.out.println();
System.out.println();
}

/**
* @param args
*/
public static void main(String[] args) {
String p = "world";
String t = "worldwideweb";

firstString = convertToChar(p);
secondString = convertToChar(t);
contains(); // true
// String p = "swag"
// String t = "volkswagen"
// contains(); false
}

public static void contains() {
boolean contains = false;
for(int i = 0; i <= firstString.length - 1; i++) {
if (firstString[i] == secondString[0]) {
containsChain(i+1, 1);
if (equals == true) {
contains = true;
}
}
}
System.out.println(contains);
}


private static void containsChain(int i, int j) {
if (j < secondString.length && i < firstString.length) {
if(firstString[i] == secondString[j]) {
equals = true;
containsChain(i + 1, j + 1);
}
else {
equals = false;
}
}
}
}

Dachte mithilfe von Rekursion könnte ich das Problem lösen aber funktioniert eben noch nicht.

Deine Erklärung leuchtet mir absolut ein aber ich weiß nicht, wie ich das implementieren soll : /

Grüße

Lukas

Answer 3

Also Rekursion ist viel zu kompliziert gedacht, einfach iterativ tuts völlig.
Grundstruktur:
2 Verschachtelte For-Schleifen:
[*]außen: Offset hochzählen
[*]innen: Buchstaben vergleichen

Als nächstes ein paar Fragen:
[*]Welchen Bereich umfasst die innere Schleife?
-> Die Länge des Needlestrings, also for (int i = 0; i < a.length(); i++), wie du im Ausgangspost schriebst.
[*]Welchen Bereich hat die äußere Schleife?
-> 0 bis Haystacklänge-Needlelänge, also for (int offs=0;offs<=b.length()-a.length();offs++)

Also fang ich mal an:

for(int offs=0;offs<=b.length()-a.length();++offs)
{
for(int i=0;i<a.length();++i)
{
if(....) //hier muss noch was hin
}
if(....) //hier auch
}

Bei welchem Fall kannst du sagen, ob ein Match vorliegt?

Kleiner Tipp noch: Das Schlüsselwort break ist hier hilfreich.

Ele