/**
* Sucht ein Stringmuster innerhalb eines Stringtextes.
*
* Aufwand: O(n*n) --> sehr schlecht!
* Optimierung:
* Alle bereits geprüften Buchstaben aus dem Stringtext gleich überspringen und
* nicht erneut mit dem ersten Buchstaben vom Stringmuster vergleichen:
* int kmp (String T, String M) {
*     //Berechne das Feld next
*     int LM = M.length(); int LT = T.length;
*     int i=0; int j=0;
*     while ((j<LM) && (i<LT))
*         if ((T.charAt(i) = M.charAt(i)) || (j=0))
*             {i++; j++;}
*         else j=next[j];
*     if (j=LM) return (i-LM);
*     else return -1;
* }
* Wobei das Feld next wie folgt berechnet wird:
* int i=1; int j=0; next[0]=0;
* while (i<LM)
*     if ((M.charAt(i) = M.charAt(j)) || (j=0))
*         {i++; j++; next[j]=j;}
*     else j=next[j]; // j ist immer kleiner!
*     
* @author Prof. V. Claus
* @version Vorlesung 01.02.207
*
*/
public class Teilwort {

    static String Text = "abcdaddeddadedaadadebjd";
    static String Muster = "ada";
   
    public static void main(String[] args) {
        String T = Text;
        String M = Muster;
        boolean enthalten = false;
        int LM = M.length();
        int LT = T.length();
       
        if (LM <= LT) {
            for (int i=0; i<LT-LM; i++)
                if (T.substring(i,i+LM-1).equals(M)) {
                    /*
                     * Vergleicht den Teilstring von T_i bis T_i+LM-1 mit dem
                     * String M.
                     * T.substring(i,j) liefert als Ergebnis einen String, der
                     * alle Methoden der Klasse String enthält, u.a. auch
                     * equals(s) zum Vergleich des Strings mit einem anderen
                     * String s.
                     */
                    System.out.println("Hurra, ab " + (i+1));
                    enthalten = true;
                }
            if (!enthalten)
                System.out.println("Nicht enthalten");
        }
    }
}