package com.jiucaiyuan.net.algrithm.sum;



/**

 * Knuth-Morris-Pratt

 *

 * 

 */

class Kmp {



    /**

     * kmp算法

     * @param haystack

     * @param needle

     * @return

     */

    public static int strStr(String haystack, String needle) {



        int n = haystack.length(), m = needle.length();

        if (m == 0) {

            return 0;

        }



        int[] pi = new int[m];

        for (int i = 1, j = 0; i < m; i++) {

            while (j > 0 && needle.charAt(i) != needle.charAt(j)) {

                j = pi[j - 1];

            }

            if (needle.charAt(i) == needle.charAt(j)) {

                j++;

            }

            pi[i] = j;

        }



        for (int i = 0, j = 0; i < n; i++) {

            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {

                j = pi[j - 1];

            }

            if (haystack.charAt(i) == needle.charAt(j)) {

                j++;

            }

            if (j == m) {

                return i - m + 1;

            }

        }



        return -1;



    }



    /**

     * 暴力破解

     * @param haystack

     * @param needle

     * @return

     */

    public static int strStr2(String haystack, String needle) {

        int n = haystack.length(), m = needle.length();

        for (int i = 0; i + m <= n; i++) {

            boolean flag = true;

            for (int j = 0; j < m; j++) {

                if (haystack.charAt(i + j) != needle.charAt(j)) {

                    flag = false;

                    break;

                }

            }

            if (flag) {

                return i;

            }

        }

        return -1;

    }





    public static void main(String[] args) {

        String haystack = "abcdefg";

        String needle = "ef";

        System.out.println("1 "+haystack + "-" + needle + "-" + strStr(haystack, needle));

        System.out.println("2 "+haystack + "-" + needle + "-" + strStr2(haystack, needle));

        haystack = "abcdefghijklmnabcdefghijklmnopqrst";

        needle = "abcdefghijklmnop";

        System.out.println("1 "+haystack + "-" + needle + "-" + strStr(haystack, needle));

        System.out.println("2 "+haystack + "-" + needle + "-" + strStr2(haystack, needle));

    }



}