Calculate the NEXT and NEXTVAL array values ​​in the exact string matching algorithm KMP

/ **

* Exact string matching algorithm kmp

* Calculate the next array of pattern string

* 1.0.1

* August 4, 2004

* arter

* arterone@hotmail.com

* this file is free software; you can redistribute it and / or modify it under the GPL.

* Copyright by Arter, 1998 - 2004

* /

#include

#include

#include

#include

Const int max_string_length = 999;

INT * GetNextArray (const char pattern []);

INT * GetNextValarray (const char pattern []);

INT WAIT ();

INT Main (int Argc, char * argv []) {

Char p [max_string_length];

INT I, M, * Next, * NextVAL

IF (argc <= 1) {

Printf ("USAGE: NEXT / N);

Printf (" / N");

Printf ("Next AbcaaAabca);

STRCPY (p, "abcaaaabca);

}

Else {

IF (Strlen (Argv [1])> MAX_STRING_LENGTH) Argv [1] [MAX_STRING_LENGTH] = '/ 0';

STRCPY (P, Argv [1]);

}

Next = getNextArray (P);

Nextval = getNextValarray (P);

M = strlen (p);

Printf ("/ n [index]:");

For (i = 0; i

Printf ("/ n [pattern]:");

For (i = 0; i

Printf ("/ n [next]:");

For (i = 0; i

Free (next);

Printf ("/ n [nextval]:");

For (i = 0; i

Free (NextVal);

Printf ("/ n");

IF (argc <= 1) Wait ();

Return 0;

}

INT * GetNextArray (const char pattern []) {

INT I, J;

Int firstIndexofpattern, lengthofpattern; int * next

Lengthofpattern = Strlen (Pattern);

IF (LengthoftPattern <= 0) {

Printf ("Error: Pattern Is Null!");

exit (0);

}

Else {

Next = (int *) malloc (intend * lengthofpattern);

FirstIndexOfPattern = 0; // The first index of array is 0 in the c language!

}

// Initialized Next [0] = -1

Next [firstindexofpattern] = firstIndexofpattern - 1;

i = next [first ";

J = firstIndexOfPattern 1;

While (j

While ((i> = firstindexofpattern) && (pattern [i]! = pattern [j-1])) {

i = next [i];

}

i ;

/ * The Difference Between "Next" and "nextval"

IF ((i <= lastindexofpattern && (pattern [i] == pattern [j])) {

Next [j] = next [i];

}

Else {* /

NEXT [J] = i;

//}

J ;

}

Return NEXT;

}

INT * GetNextValarray (const char pattern []) {

INT I, J;

Int firstIndexofpattern, Lengthofpattern;

INT * NEXTVAL;

Lengthofpattern = Strlen (Pattern);

IF (LengthoftPattern <= 0) {

Printf ("Error: Pattern Is Null!");

exit (0);

}

Else {

Nextval = (int *) Malloc (intend * lengthofpattern);

FirstIndexOfPattern = 0; // The first index of array is 0 in the c language!

}

// Initialized Next [0] = -1

NextVal [firstIndexofpattern] = firstIndexOfpattern - 1;

i = nextVal [firstVal [first virtnexofpattern];

J = firstIndexOfPattern 1;

While (j

While ((i> = firstindexofpattern) && (pattern [i]! = pattern [j-1])) {

i = nextVal [i];

}

i ;

IF (Pattern [i] == Pattern [J]) {

NextVal [J] = nextVal [i];

Else {

NEXTVAL [J] = i;

}

J ;

}

Return nextVal;

}

INT WAIT () {

Printf ("/ n ");

GetChar ();

Return 1;

}