class Main{

    static public int[] getNext(String p){
        int len = p.length();
        int[] next = new int[len];
        next[0] = -1;
        int j = -1;
        for(int i=1; i<len; i++){
            while(j!=-1&&p.charAt(j+1)!=p.charAt(i)) j = next[j];
            if(p.charAt(j+1)==p.charAt(i)) next[i] = ++j;
        }
        return next;
    }

    public static void main(String[] args){
        String s = "abcabcaab";
        String p = "ab";
        int len1 = s.length();
        int len2 = p.length();
        int j = -1;
        int[] next = getNext(p);
        for(int i=0; i<len1; i++){
            while(j!=-1&&s.charAt(i)!=p.charAt(j+1)) j = next[j];
            if(s.charAt(i)==p.charAt(j+1)) j++;
            if(j==len2-1){
                System.out.println("true" + i);
                j = next[j];
            }
        }
    }
}