// 輸入 p長度 p s長度 s
3
aba
5
ababa
    
// 輸出結(jié)果
0 2

// 下面為偽代碼，只是起到思路作用

// 首先我們需要創(chuàng)造s[],p[]，并賦值
S[N],P[N]
    
// 然后我們開始匹配，我們會從S的第一個字符開始匹配，設(shè)置一個flag判斷該字符開始的字符串是否與P字符匹配
// 該算法從每個i開始，全部進(jìn)行匹配
for(int i = 1;i <= n;i++ ){
    boolean flag = true;
    for(int j = 1;j <= m;j++){
        if(s[i+j-1] != p[j]){
            flag = false;
            break;
        }
    }
}

// 我們給出一套完整的暴力求解方法

/**

 * 暴力破解法

 * @param ts 主串

 * @param ps 模式串

 * @return 如果找到，返回在主串中第一個字符出現(xiàn)的下標(biāo)，否則為-1

 */

public static int bf(String ts, String ps) {

    char[] t = ts.toCharArray();

    char[] p = ps.toCharArray();

    int i = 0; // 主串的位置

    int j = 0; // 模式串的位置

    while (i < t.length && j < p.length) {

       if (t[i] == p[j]) { 
           
           // 當(dāng)兩個字符相同，就比較下一個
           i++;
           j++;

       } else {

           i = i - j + 1; // 一旦不匹配，i后退（從之前i的下一位開始，也是遍歷所有i）

           j = 0; // j歸0
       }
    }

    // 當(dāng)上面循環(huán)結(jié)束，必定是i到頭或者j到頭，如果是j到頭，則說明存在子串符合父串，我們就將頭位置i返回
    if (j == p.length) {
       return i - j;
    } else {
       return -1;
    }

}

// 但是我們會發(fā)現(xiàn)：我們可以不讓i回退而是讓j回退，使j回退到能夠與當(dāng)前i相匹配的點位，然后繼續(xù)進(jìn)行主串和模式串的匹配

// 首先我們給出一個next手寫實例

/*
模板串為：ABABAA
    
next[0]代表t[0]-t[0]，即"A" , "A"的前綴和后綴都為空集，共有元素的長度為0.

next[1]代表t[0]-t[1]，即"AB"，前綴為“A”，后綴為“B”,共有元素的長度為0..

next[2]代表t[0]~t[2]，即"ABA"，前綴為“AB"，后綴為"BA"，最大前后綴即"A",長度為1.

next[3]代表t[0]~t[3]，即"ABAB"，前綴為"ABA"后綴為"BAB”,最大前后綴即"AB ",長度為2.

next[4]代表t[0]~t[4]，即"ABABA",前綴為"ABAB"，后綴為"BABA",最大前后綴即" ABA",長度為3.

next[5]代表t[0]-t[5]，即" ABABAA",前綴為“ABABA",T后綴為“BABAA";最大前后綴即"A",長度為1.

*/

// 我們next的作用是使next[j]=k使 P[0 ~ k-1] == P[j-k ~ j-1]、
// 當(dāng)?shù)趎個數(shù)不匹配時，我們讓j回退到k，這時我們的主串和模式串的前綴還屬于匹配狀態(tài)，我們繼續(xù)進(jìn)行匹配
例如 ababc
    我們?nèi)绻ヅ涞絚不符合時，我們可以使j回退到k（這里的k是2，即a）再繼續(xù)進(jìn)行匹配
    因為我們的c前面的ab和開頭的ab是匹配的，我們主串中的i前面肯定也是ab，我們的l前面也是ab，所以兩者匹配，我們可以繼續(xù)后面的匹配
    相當(dāng)于我們的x不變，我們將j放在2的位置，前面的ab已完成匹配，我們只需要匹配abc即可

// 公式書寫就是下述：
    
當(dāng)T[i] != P[j]時

有T[i-j ~ i-1] == P[0 ~ j-1]

由P[0 ~ k-1] == P[j-k ~ j-1]

必然：T[i-k ~ i-1] == P[0 ~ k-1]

public static int[] getNext(String ps) {

    char[] p = ps.toCharArray();

    int[] next = new int[p.length];

    // 這里的next[0]需要等于-1
    // 因為j在最左邊時，不可能再移動j了，這時候要應(yīng)該是i指針后移。所以在代碼中才會有next[0] = -1;這個初始化。
    next[0] = -1;

    // 這里設(shè)置j的初始值從第一個開始（我們需要得到全部next數(shù)組）
    int j = 0;

    // 這里設(shè)置k，k就是應(yīng)該返回的位置，也就是我們常說的前綴和后綴匹配區(qū)域的前綴的后一個位置
    int k = -1;

    // 進(jìn)行循環(huán)，得到next數(shù)組
    while (j < p.length - 1) {

        // 首先是k==-1時，說明前面已無匹配狀態(tài)，我們重新開始
        // 然后是p[j] == p[k]，說明循環(huán)時新添加的值，與我們應(yīng)該返回比對的位置相同
        // 同時由于我們之前的部分都是已經(jīng)匹配成功的，所以加上這個數(shù)使我們的匹配長度又增加一位
       if (k == -1 || p[j] == p[k]) {

           // 當(dāng)兩個字符相等時要跳過（因為p[k]與S[i]不符合的話，由于我們的p[j]=p[k]，所以肯定也不符合，我們直接跳下一步）
           if (p[++j] == p[++k]) { 

              next[j] = next[k];

           } else {
			// 因為在P[j]之前已經(jīng)有P[0 ~ k-1] == p[j-k ~ j-1]。（next[j] == k）
			// 這時候現(xiàn)有P[k] == P[j]，我們是不是可以得到P[0 ~ k-1] + P[k] == p[j-k ~ j-1] + P[j]。
       		// 即：P[0 ~ k] == P[j-k ~ j]，即next[j+1] == k + 1 == next[j] + 1
            // 前面我們已經(jīng)進(jìn)行了j++和k++，所以這里直接賦值即可
              next[j] = k;

           }

       } else {
		// 如果當(dāng)前狀態(tài)無法匹配，我們就跳回上一個前綴后綴相同部分再來判斷是否前后綴相同
           k = next[k];

       }

    }

    return next;

} 

/*該代碼實際上是由暴力求解代碼改造過來的*/

public static int KMP(String ts, String ps) {

    char[] t = ts.toCharArray();

    char[] p = ps.toCharArray();

    int i = 0; // 主串的位置

    int j = 0; // 模式串的位置

    int[] next = getNext(ps);
    
    // 開始判斷（設(shè)置邊界值）
    while (i < t.length && j < p.length) {

        // 當(dāng)j為-1時，要移動的是i，當(dāng)然j也要歸0
        // 如果匹配成功，兩者都進(jìn)行移動，開始下一位比對
       if (j == -1 || t[i] == p[j]) { 

           i++;

           j++;

       } else {
		   // 如果比對失敗，我們將 j 返回next數(shù)組指定位置繼續(xù)匹配
           
           // i不需要回溯了
           // i = i - j + 1;

           j = next[j]; // j回到指定位置

       }

    }

    // 最后同樣進(jìn)行判斷，是否符合條件
    if (j == p.length) {

       return i - j;

    } else {

       return -1;

    }

}

import java.util.Scanner;

class ppp {

    /**
     * 主代碼
     * @param args
     */
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        String ts = scanner.nextLine();

        String ps = scanner.nextLine();

        int kmp = KMP(ts, ps);

        System.out.println(kmp);
    }

    /**
     * kmp算法
     * @param ts
     * @param ps
     * @return
     */
    public static int KMP(String ts, String ps) {

        char[] t = ts.toCharArray();

        char[] p = ps.toCharArray();

        int i = 0; // 主串的位置

        int j = 0; // 模式串的位置

        int[] next = getNext(ps);

        // 開始判斷（設(shè)置邊界值）
        while (i < t.length && j < p.length) {

            // 當(dāng)j為-1時，要移動的是i，當(dāng)然j也要歸0
            // 如果匹配成功，兩者都進(jìn)行移動，開始下一位比對
            if (j == -1 || t[i] == p[j]) {

                i++;

                j++;

            } else {
                // 如果比對失敗，我們將 j 返回next數(shù)組指定位置繼續(xù)匹配

                // i不需要回溯了
                // i = i - j + 1;

                j = next[j]; // j回到指定位置

            }

        }

        // 最后同樣進(jìn)行判斷，是否符合條件
        if (j == p.length) {

            return i - j;

        } else {

            return -1;

        }

    }

    /**
     * next數(shù)組求解
     * @param ps
     * @return
     */
    public static int[] getNext(String ps) {

        char[] p = ps.toCharArray();

        int[] next = new int[p.length];

        // 這里的next[0]需要等于-1
        // 因為j在最左邊時，不可能再移動j了，這時候要應(yīng)該是i指針后移。所以在代碼中才會有next[0] = -1;這個初始化。
        next[0] = -1;

        // 這里設(shè)置j的初始值從第一個開始（我們需要得到全部next數(shù)組）
        int j = 0;

        // 這里設(shè)置k，k就是應(yīng)該返回的位置，也就是我們常說的前綴和后綴匹配區(qū)域的前綴的后一個位置
        int k = -1;

        // 進(jìn)行循環(huán)，得到next數(shù)組
        while (j < p.length - 1) {

            // 首先是k==-1時，說明前面已無匹配狀態(tài)，我們重新開始
            // 然后是p[j] == p[k]，說明循環(huán)時新添加的值，與我們應(yīng)該返回比對的位置相同
            // 同時由于我們之前的部分都是已經(jīng)匹配成功的，所以加上這個數(shù)使我們的匹配長度又增加一位
            if (k == -1 || p[j] == p[k]) {

                // 當(dāng)兩個字符相等時要跳過
                //（因為p[k]與S[i]不符合的話，由于我們的p[j]=p[k]，所以肯定也不符合，我們直接跳下一步）
                if (p[++j] == p[++k]) {

                    next[j] = next[k];

                } else {
                    // 因為在P[j]之前已經(jīng)有P[0 ~ k-1] == p[j-k ~ j-1]。（next[j] == k）
                    // 這時候現(xiàn)有P[k] == P[j]，我們是不是可以得到P[0 ~ k-1] + P[k] == p[j-k ~ j-1] + P[j]。
                    // 即：P[0 ~ k] == P[j-k ~ j]，即next[j+1] == k + 1 == next[j] + 1
                    // 前面我們已經(jīng)進(jìn)行了j++和k++，所以這里直接賦值即可
                    next[j] = k;

                }

            } else {
                // 如果當(dāng)前狀態(tài)無法匹配，我們就跳回上一個前綴后綴相同部分再來判斷是否前后綴相同
                k = next[k];

            }

        }

        return next;

    }
}