KMP

    xiaoxiao2022-08-06  8


    某平台价值19860元的编程课程资料免费领取【点我领取】


    KMP算法

    KMP原理

    KMPnext

    public static void main(String[] args) { String a="VERDI"; char[] pattern=a.toCharArray(); int[] prefix=next(pattern); String b="AXIVVERDIYERDIAN"; char[] original=b.toCharArray(); System.out.println(SearchPattern(original, pattern)); } public static int SearchPattern(char[] original,char[] pattern){ int[] next=next(pattern); int j = 0; for (int i = 0; i < original.length; i++) { while (j > 0 && original[i]!= pattern[j]) j = next[j-1]; if (original[i] == pattern[j]) j++; if (j == pattern.length) { //System.out.println("find at position " + (i - j)); //System.out.println(original.subSequence(i-j+ 1, i + 1)); //j = next[j]; return i-j+1; } } return 0; } public static int[] next(char[] pattern){ int length=pattern.length; int[] prefix=new int[length]; prefix[0]=0; for(int i=1; i<length; i++) { int k=prefix[i-1]; //不断递归判断是否存在子对称,k=0说明不再有子对称,Pattern[i] != Pattern[k]说明虽然对称,但是对称后面的值和当前的字符值不相等,所以继续递推 while( pattern[i] != pattern[k] && k!=0 ) k=prefix[k-1]; //继续递归 if( pattern[i] == pattern[k])//找到了这个子对称,或者是直接继承了前面的对称性,这两种都在前面的基础上++ prefix[i]=k+1; else prefix[i]=0; //如果遍历了所有子对称都无效,说明这个新字符不具有对称性,清0 } return prefix; } }
    转载请注明原文地址: https://ju.6miu.com/read-1132111.html
    最新回复(0)