模式串t="abaaabb"在kmp模式匹配算法中,该模式串的next函数值分别是

next[0]:0

next[1]:0

next[2]:0

next[3]:1

next[4]:1

next[5]:1

next[6]:2

附代码：

void getfailed(charst){

f[1]=f[0]=0;

for(int i=2;i<strlen(st);i++){

int j=f[i-1];

while(j&&st[j]!=st[i-1])j=f[j];

f[i]=st[j]==st[i-1]j+1:0;

}

}

一种由Knuth(DEKnuth)、Morris(JHMorris）和Pratt(VRPratt）三人设计的线性时间字符串匹配算法。这个算法不用计算变迁函数δ，匹配时间为Θ（n），只用到辅助函数π[1，m]，它是在Θ（m）时间内，根据模式预先计算出来的。数组π使得我们可以按需要，“现场”有效的计算（在平摊意义上来说）变迁函数δ。粗略地说，对任意状态q=0，1，…，m和任意字符a∈Σ，π[q]的值包含了与a无关但在计算δ（q，a）时需要的信息。由于数组π只有m个元素，而δ有Θ（m∣Σ∣）个值，所以通过预先计算π而不是δ，使得时间减少了一个Σ因子。

求next程序代码：

void  getNext(charp,intnext) 

{     

    int   j,k;     

    next[0]=-1; j=0;k=-1;   

    while(j<strlen(p)-1)

    {         

        if(k==-1||p[j]==p[k])    //匹配的情况下,p[j]==p[k]         

        {           

             j++;             

             k++;             

             next[j]=k;         

        }         

        else          //p[j]!=p[k]             

            k=next[k];     

    } 

}   

KMP算法主程序：

int   KMPMatch(chars, charp)

{     

    int    next[100];     

    int    i,j;  i=0;  j=0;     

    getNext( p, next );   

    while( i < strlen(s) ){         

        if(j==-1||s[i]==p[j])         

        {           

            i++;             

            j++;         

        }

        else

        {             

            j=next[j];       //消除了指针i的回溯         

        }         

        if(j==strlen(p))           

            return    i-strlen(p);     

    }     

    return-1; 

}   

public class KMP_Impl {

static String modelStr = "ababab";

static String modelStr1 = "abcabcab";

static String modelStr2 = "abcabdab";

static String sourceStr = "abcdabcabababc";

static String sourceStr1 = "abcaabababcabababc";

static String sourceStr2 = "ababcaabaabaababcabababc";

//seek model string next position of comparing

public int[] nextPoint(String mod) {

//declare array recording all next char match points

int[] next = new int[modlength()];

//define first char index

int j = 0;

for (int i = 0; i < modlength(); i++) {

//first char seeks last same char position, that's itself

if (i == 0) {

next[i] = 0;

continue;

}

//if first char finds same char in following position, it should seek same second char position

//for example 'abab', when first 'a' finds second 'a', j index will move to next and see if first 'b'

//will equal to next position(i+1)

//if there is a unequality during match-seeking, move to first char(j=0) and start again

if (modcharAt(i) == modcharAt(j)) {

next[i] = j;

j++;

} else {

j = 0;

next[i] = j;

}

}

return next;

}

//KMP match

public int KMP_match(String src, String mod) {

int[] nextPosition = nextPoint(mod);

int i = 0;

int j = 0;

//counting of matching time

int count = -1;

while(i < srclength()) {

count++;

//if model string move to end, that says a successful match

//return the first match char position(i-j)

if (j == modlength()) {

Systemoutprintln("count time is " + count);

return i - j;

}

//from the first chars of two string(src and mod), compare every char

//if there is a hit in any position, check next close poistion(j++ i++)

//else compare current i position and next j position

// Systemoutprintln("src char is " + srccharAt(i) + " mod char is " + modcharAt(j));

if (srccharAt(i) == modcharAt(j)) {

i++;

j++;

} else {

j = nextPosition[j];

if(srccharAt(i) != modcharAt(j)) {

i++;

j = 0;

}

}

}

// for (int i = 0; i < srclength(); i++) {

// count++;

// //if model string move to end, that says a successful match

// //return the first match char position(i-j)

// if (j == modlength()) {

// Systemoutprintln("count time is " + count);

// return i - j;

// }

//

// //from the first chars of two string(src and mod), compare every char

// //if there is a hit in any position, check next close poistion(j++ i++)

// //else compare current i position and next j position

// Systemoutprintln("src char is " + srccharAt(i) + " mod char is " + modcharAt(j));

// if (srccharAt(i) == modcharAt(j)) {

// j++;

// } else {

// j = nextPosition[j];

// if (srccharAt(i) == modcharAt(j)) {

// Systemoutprintln("src char is " + srccharAt(i) + " mod char is " + modcharAt(j));

// j++;

// } else {

// j = 0

// }

//

// }

Systemoutprintln("count time is " + count);

return -1;

}

public static void dump(String model) {

int[] next = new KMP_Impl()nextPoint(model);

for (int i : next) {

Systemoutprint(i);

}

Systemoutprintln();

Systemoutprintln(model);

}

public static void main(String args) {

KMP_Impldump(modelStr);

KMP_Impldump(modelStr1);

KMP_Impldump(modelStr2);

Systemoutprintln(new KMP_Impl()KMP_match(sourceStr, modelStr));

Systemoutprintln(new KMP_Impl()KMP_match(sourceStr1, modelStr));

Systemoutprintln(new KMP_Impl()KMP_match(sourceStr2, modelStr));

// String src = "aabaabhijklmnhijcbahijklmnhijkabcccccc";

// String target = "hijklmnhijk";

//KMP_Impldump(target);

//Systemoutprintln(new KMP_Impl()KMP_match(src, target));

}

}

上代码,有详细说明

public class KMP {

String model = "abcdabce";

// String model = "abcabcabd";

// String model = "aaaab";

// String model = "asdaaaaaaabdabcabcaabaaaaaskdf";

char[] tempModel = modeltoCharArray();

String str = "asdaaaaaaabdabcabcaabaaaaaskdf";

char[] tempStr = strtoCharArray();

int[] backto = new int[modellength()];

int[] next = new int[modellength()];

//查找用例

public void findStr(){

int i=0;

int j=0;

while(i<tempStrlength){

if(tempStr[i] == tempModel[j]){

i++;

j++;

}else{

j = backto[j];

if(j<0){

i++;

j++;

}

}

if(j == tempModellength){

Systemoutprintln(i+" "+tempStr[i-1]);

j=0;

}

}

}

/

a a a a b

-1 -1 -1 -1 3

a b c d a b c e

-1 0 0 0 -1 0 0 3

/

public void next(){

int i=0, //模式串下标,即当前位置开始为0

k=-1;//k表示字符串在位置i之前已匹配的子串最长长度类似于模式串的下标(从0开始)

next[i]=-1;//第一个next为-1

while(i+1<tempModellength){//i 模式串的当前位置,因为第一个next为-1,所以从第二个开始,往前查找模式长度

if(k == -1 //初始,k,i直接自加:k=0,i=1

|| tempModel[k] == tempModel[i]){//比较第k个字符和第i个字符

i++;

k++;

if(tempModel[k] != tempModel[i]){//比较第k+1个字符和第i+1个字符不相等,说明k为当前模式最长长度

next[i] = k;//k最小为0,因为i是从第二个开始的

}else{//第k+1个字符和第i+1个字符相等,说明第i+1个字符比较不同后,可后推到第next[k]个字符开始比较

next[i] = next[k];

}

}else{//往后找k值,此时k值表现为模式串的下标

k = next[k];

}

}

}

public void start(){

Systemoutprintln("--------------------------------");

next();

//CommonUtilprintCharAndIntArray(tempModel,next);

}

public static void main(String[] args){

new KMP()start();

}

}