kmp算法,求重复字符串

public class Demo {

    public static void main(String[] args) {

        String s1 = "ADBCFHABESCACDABCDABCE";

        String s2 = "ABCDABCE";

        int i = kmp(s1, s2);

        System.out.println("下标 i="+i+"  对应字符串："+s1.substring(14));

    }

    public static int kmp(String s1, String s2) {

        char[] c1 = s1.toCharArray();

        char[] c2 = s2.toCharArray();

        int[] next=getNext(s2);

        int i=0,j=0;

        while (i < c1.length && j <c2.length)

        {

            if (j == -1 || c1[i] == c2[j]) {

                i++;

                j++;

            } else {

                j = next[j];

            }

        }

        if (j == c2.length)

            return i - j;

        else

            return -1;

    }

    public static int[] getNext(String s) {

        char[] chars = s.toCharArray();

        int[] arr = new int[chars.length];

        arr[0] = -1;

        int k = -1;

        int j = 0;

        while (j < chars.length - 1) {

            //chars[k]表示前缀，chars[j]表示后缀

            if (k == -1 || chars[j] == chars[k]) {

                ++k;

                ++j;

                arr[j] = k;

            } else {

                k = arr[k];

            }

            System.out.println(Arrays.toString(arr));

        }

        return arr;

    }

}
巴特西

kmp算法,求重复字符串

最新文章

热门文章
