class SucheT {

  static final String text1 = "PETER PIPER PICKED A PECK";
                             //0123456789012345678901234567890
  static final String text2 = "FISCHERS FRITZ FISCHT FRISCHE FISCHE";
                             //0123456789012345678901234567890123456789
  static final String text3 = "00100111010010100010100111000111";
                             //0123456789012345678901234567890123456789                             
                             
  static final String muster1 = "PECK";
  static final String muster2 = "SCAMPI";
  static final String muster3 = "FISCHT";
  static final String muster4 = "10100111";
  
  static int [] sprung;
  static int min;
  static int max;
  static int mL;
  
  static void initSprung(String muster){
    max = 0;
    min = 65536;
    for(int mPos=0; mPos < (mL-1);mPos++){
     	int c = muster.charAt(mPos);
     	if (c > max) max=c;
     	if (c < min) min=c;
      }
    int aL = 1+max-min;
    sprung = new int[aL];
    for(int k=0;k<aL;k++)sprung[k]=mL;
    for(int mPos=0; mPos < (mL-1);mPos++)
		     sprung[muster.charAt(mPos)-min] = (mL-1)-mPos;
    }
    
  static int getSprung(int c){
    if ((c<min)||(c>max)) return mL;
    return sprung[c-min];
    }  
  
  static int bmSuche(String text, String muster){
		mL = muster.length();
		int tL = text.length();
		int dL = tL - mL; // Delta
		if ((mL >0) && (dL >=0)){
		  initSprung(muster);
		  //for(int k=0;k<200;k++)System.out.println(k+" ("+(char) k+") : "+sprung[k]);
		  int tPos = 0; // Index im text - String
		  while(tPos <= dL){
			  int mPos = mL-1; // Index im muster - String
		    while((mPos>= 0) && (text.charAt(tPos+mPos) == muster.charAt(mPos))) mPos--; 
				if (mPos == -1) return tPos; // muster gefunden
			  else tPos += getSprung(text.charAt(tPos+mL-1));
			  }
		  
		  }
		return -1;
		}

    static void testSuche(String text, String muster){
    	int index = bmSuche(text, muster);
    	System.out.println("Text:   \""+text+"\"");
    	System.out.println("Muster: \""+muster+"\"");
      if (index >= 0) System.out.println("Gefunden auf Position: "+index);
      else System.out.println("Nicht gefunden.");
    }
    
    
    
    public static void main(String ... args) {
        System.out.println("Anfang String Such tester"); 
        testSuche(text1, muster1);
        testSuche(text2, muster2);
        testSuche(text2, muster3);
        testSuche(text3, muster4);
        System.out.println("Ende String Such tester");   
    }
}