import java.awt.*;
import java.io.IOException;

class Suchen{
char[] tabelle;
Suchen(String s){
    tabelle = s.toCharArray();
    }

int bfSuche(String muster){
		int musterLaenge = muster.length();
		int tabLaenge = tabelle.length;
		if ((musterLaenge > 0) && (musterLaenge <= tabLaenge)){
			int tabPos = 0;
			int musterPos = 0;
			while((musterPos < musterLaenge)&&(tabPos < tabLaenge))
				if (tabelle[tabPos] == muster.charAt(musterPos)){
					tabPos++; 
					musterPos++;
					}
				else{
					tabPos -= musterPos-1;
					musterPos = 0;
					}
			if(musterPos>=musterLaenge) return tabPos-musterLaenge;
			}
		return -1;
		}

int bm1Suche(String muster){

		int musterLaenge = muster.length();
		int tabLaenge = tabelle.length;
		char[] delta1Tab = baueDelta1Tab(muster);
		if ((musterLaenge > 0) && (musterLaenge <= tabLaenge)){
			int tabPos = musterLaenge-1;
			int musterPos = 0;
			while( tabPos < tabLaenge){
				musterPos = musterLaenge-1;
				int tabPosAlt = tabPos;
				while (tabelle[tabPos] == muster.charAt(musterPos)){
					if (musterPos == 0) return tabPos;
					musterPos--;
					tabPos--;
					}
				tabPos = tabPosAlt + delta1Tab[tabelle[tabPosAlt]];
				}
			}
		return -1;
		}

 /*int BM2Suche(String Muster){
    int MusterLaenge = Muster.length();
    int TabLaenge = Tabelle.length;
    char[] Delta1Tab = BaueDelta1Tab(Muster);
    int[]  Delta2Tab = BaueDelta2Tab(Muster);
    // for (int i = 0; i < MusterLaenge; i++) System.out.println(Delta2Tab[i]);
    if ((MusterLaenge > 0) && (MusterLaenge <= TabLaenge)){
        int TabPos = MusterLaenge-1;
        System.out.println("TabPos = "+TabPos);
        int MusterPos = 0;
        while( TabPos < TabLaenge){
            MusterPos = MusterLaenge-1;
            int TabPosAlt = TabPos;
            while (Tabelle[TabPos] == Muster.charAt(MusterPos)){
                if (MusterPos == 0) return TabPos;
                MusterPos--;
                TabPos--;
                }
            int tbn1 = TabPosAlt + Delta1Tab[Tabelle[TabPosAlt]];
            int tbn2 = TabPos    + Delta2Tab[MusterPos];
            TabPos = Math.max(tbn1, tbn2);
            System.out.println("TabPos = "+TabPos);
            }
        }
    return -1;
    }*/

    char[] baueDelta1Tab(String muster){

		int ls = muster.length();
		char[] deltaTab = new char[256];
		for (int i = 0; i < 256; i++) deltaTab[i] = (char) ls;
		for (int i = 1; i < ls; i++) 
			deltaTab[muster.charAt(i-1)] = (char) (ls - i) ;
		return deltaTab;
		}

    /*int[] BaueDelta2Tab(String Muster){
      int ls = Muster.length();
      int ms = ls - 1;
      int Index = ms;
      int Shift = ls;
      int[] DeltaTab = new int[ls];
      int[] nTab = new int[ls];
      for (int i = 0; i < ls; i++) DeltaTab[i] = 2*ms - i;
      while (Index >= 0){
        nTab[Index] = Shift;
        while(( Shift < ls) && (Muster.charAt(Index) != Muster.charAt(Shift))){
            DeltaTab[Shift] = Math.min(DeltaTab[Shift], ms -Index);
            Shift = nTab[Shift];
            }
        if (Index > 0) { Shift--; Index--;}
        else break;
        }
      for (int i = 0; i < Shift; i++) DeltaTab[i] = Math.min(DeltaTab[i], ls + Shift - i);
      return DeltaTab;
    }*/

}


public class SucheT {

    public static void main(String args[]) {
        System.out.println("String Such Tester");
        String tab1 = "PETER PIPER PICKED A PECK";
                     //0123456789012345678901234567890
        String such1 = "PECK";
        String tab2 = "00100111010010100010100111000111";
                     //012345678901234567890123456789012
        String such2 = "10100111";
        String tab  = tab2;
        String such = such2;
        Suchen meineSuche = new Suchen(tab);
        int index;

        index = meineSuche.bfSuche(such);
        if (index >= 0) System.out.println("Gefunden auf Position: "+index);
        else System.out.println("Nicht gefunden.");

        index = meineSuche.bm1Suche(such);
        if (index >= 0) System.out.println("Gefunden auf Position: "+index);
        else System.out.println("Nicht gefunden.");

        /*index = MeineSuche.BM2Suche(Such);
        if (index >= 0) System.out.println("Gefunden auf Position: "+index);
        else System.out.println("Nicht gefunden.");*/

        System.out.println("");
        System.out.println("(press Enter to exit)");
        try {
            System.in.read();
        } catch (IOException e) {
            return;
        }
    }
}