static int kmpSearch(String pat, String text) {
        int n = text.length();
        int m = pat.length();
        int[] trans = new int[m + 1];  // オートマトンの遷移テーブルを作る
        trans[0] = -1;
        for (int i = 2; i <= m; i++) {
            char c = pat.charAt(i - 1);
            int fall = trans[i - 1];
            while (fall != -1 && c != pat.charAt(fall))
                fall = trans[fall];  // 次の位置が見つかるまで戻る
            trans[i] = fall + 1;
        }

        int st = 0;  // 現在のステート
        int count = 0;
        for (int i = 0; i < n; i++) {
            // オートマトンの文字と一致するまで戻り続ける
            while (st >= 0 && text.charAt(i) != pat.charAt(st))
                st = trans[st];
            if (++st >= m) {  // 受理状態
                // ここで何か処理する
                count++;
                st = trans[st];
            }
        }
        return count;
    }