Java's indexOf-Methode implementieren (Substring-Suche)

Question

Ich bin nur ein CS-Student des zweiten Semesters und kann keine der bekannten effizienten Teilstringsuchalgorithmen verwenden. Ich muss die Methode indexOf mit der folgenden Methodensignatur implementieren:

int indexOf(String str, String pattern), die den Index der ersten Stelle, an der Muster als Teilzeichenfolge von str erscheint.

Dies ist, was ich versucht:

Zuerst habe ich erstellt indexOf(String str, char ch, int startIndex) eine überladene Methode Index mit der Signatur, die den Index der ersten Stelle von char zurück oder -1 sonst.

private int indexOf(String str, char ch, int startIndex) { 
    for(int i = startIndex; i < str.length(); i++) 
     if(str.charAt(i) == ch) return i; 

    return -1; 
} 

Jetzt schreibe ich die Methode, die nach einer Teilsucht (pattern).

private int indexOf(String str, String pattern) { 
    int headIndex = indexOf(str, pattern.charAt(0), 0); 
    int tailIndex = indexOf(str, pattern.charAt(pattern.length() - 1), 0); 

    if(headIndex == -1 || tailIndex == -1) return -1; // no substring match 

    while(true) { 
     int j = 0; 
     for(int i = headIndex; i <= tailIndex; i++) 
      if(str.charAt(headIndex) != pattern.charAt(j++)) { //if substring does not match then compute a new head and tail Index 
       headIndex = indexOf(str, pattern.charAt(0), headIndex); 
       tailIndex = indexOf(str, pattern.charAt(pattern.length() - 1), tailIndex); 
       j = 0; 
       i = headIndex + 1; 
       if(headIndex == -1 || tailIndex == -1) return -1; 
       break; 
      } 

     if(headIndex >= 0) return headIndex; 
    } 
} 

Ich glaube, ich bin in der Nähe aber ruft wie indexOf("Hellolo", "lo") kehrt 2 statt 3. Ich versuche, herauszufinden, wo ich mit meiner Logik falsch gelaufen ist und Hilfe brauchen, so zu tun.

Ich darf keine speziellen String-Methoden außer Länge verwenden.

Answer 1

indexOf("Hellolo", "lo") den Wert 2, weil der Zähler Null basiert ... hier die doc

public int indexOf(int ch) 

Gibt den Index innerhalb dieser Zeichenfolge des ersten Auftretens des angegebenen Zeichen. Wenn ein Zeichen mit dem Wert ch in der Zeichenfolge auftritt, die von diesem String-Objekt dargestellt wird, wird der Index (in Unicode-Code-Einheiten) des ersten solchen Vorkommens zurückgegeben. Für Werte von ch im Bereich von 0 bis 0xFFFF (einschließlich),

Answer 2

In Ihrem Code Sie suchen für den ersten Index eines einzelnen Zeichens anstelle einer Zeichenfolge.

int headIndex = indexOf(str, pattern.charAt(0), 0); 

Wenn wir davon ausgehen, dass str = Hellolo" und pattern = "lo" dann oberhalb der Code sucht die l und nicht die lo.

Edit: Wenn Sie zum ersten Vorkommen der Zeichenfolge aussehen wollen "lo" dann müssen Sie

int headIndex = indexOf(str, pattern, 0); 

Answer 3

den Code ändern Ich würde nur den Code in so einfach wie nur irgend möglich schreiben.

package com.ggl.testing; 

public class MyString { 

    public static void main(String[] args) { 
     MyString myString = new MyString(); 
     String string = "abcdefghij"; 
     String pattern = "defg"; 
     System.out.println(myString.indexOf(string, pattern)); 

     pattern = "ghij"; 
     System.out.println(myString.indexOf(string, pattern)); 

     pattern = "asdf"; 
     System.out.println(myString.indexOf(string, pattern)); 
    } 

    public int indexOf(String string, String pattern) { 
     int length = string.length() - pattern.length(); 
     for (int index = 0; index <= length; index++) { 
      if (patternMatch(string, index, pattern)) { 
       return index; 
      } 
     } 

     return -1; 
    } 

    private boolean patternMatch(String string, int index, String pattern) { 
     int i = index; 
     for (int j = 0; j < pattern.length(); j++) { 
      if (string.charAt(i) != pattern.charAt(j)) { 
       return false; 
      } 
      i++; 
     } 

     return true; 
    } 

} 

Answer 4

int headIndex = indexOf(str, pattern.charAt(0)); 
int tailIndex = indexOf(str, pattern.charAt(pattern.length() - 1)); 

if(headIndex == -1 || tailIndex == -1) return -1; // no substring match 

Buggy -> betrachten diesen Fall:

String str = "nevern"; 
String pattern = "vern"; 

ich auf den Kopf char denken konzentriert genug:

public class Search { 


    static private int indexOf(String src, char ch, int startIndex) { 
     for(int i = startIndex; i < src.length(); i++) 
      if(src.charAt(i) == ch) return i; 

     return -1; 
    } 

    static private int indexOf(String src, String pat) { 
     int head_in_src = 0; 

     while (-1 != (head_in_src = indexOf(src, pat.charAt(0), head_in_src))) { 
      if (head_in_src + pat.length() > src.length() - head_in_src) 
       return -1; 
      boolean match = true; 
      int offset = 0; 
      for (; offset < pat.length(); offset++) { 
       if (src.charAt(offset + head_in_src) != pat.charAt(offset)) { 
        match = false; 
        break; 
       } 
      } 
      if (true == match) 
       return head_in_src; 
      head_in_src += offset; 
     } 
     return -1; 
    } 

    public static void main(String[] args) { 
     String src = "ne-nevern-nevern"; 
     String pat = "ever"; 
     String pat1 = "ne"; 
     String pat2 = "vern"; 
     String pat3 = "everne"; 
     String pat4= "-ne-"; 
     String pat5= "ner"; 

     System.out.printf("src=%1$s, pat=%2$s, index=%3$d%n", src, pat, indexOf(src, pat)); 
     System.out.printf("src=%1$s, pat1=%2$s, index=%3$d%n", src, pat1, indexOf(src, pat1)); 
     System.out.printf("src=%1$s, pat2=%2$s, index=%3$d%n", src, pat2, indexOf(src, pat2)); 
     System.out.printf("src=%1$s, pat3=%2$s, index=%3$d%n", src, pat3, indexOf(src, pat3)); 
     System.out.printf("src=%1$s, pat4=%2$s, index=%3$d%n", src, pat4, indexOf(src, pat4)); 
     System.out.printf("src=%1$s, pat5=%2$s, index=%3$d%n", src, pat5, indexOf(src, pat5)); 
    } 
} 

Ausgang:

src=ne-nevern-nevern, pat=ever, index=4 
src=ne-nevern-nevern, pat1=ne, index=0 
src=ne-nevern-nevern, pat2=vern, index=5 
src=ne-nevern-nevern, pat3=everne, index=-1 
src=ne-nevern-nevern, pat4=-ne-, index=-1 
src=ne-nevern-nevern, pat5=ner, index=-1