ReZero's Utopia.

KMP

Word count: 126Reading time: 1 min
2019/09/18 Share

How to calc the next array.

  1. Calc the max length of suffix and prefix as follows:

    string a b a a b c a b a
    length 0 0 1 1 2 0 1 2 3
    next -1 0 0 1 1 2 0 1 2

    As you can see, the next array is the suffix equals prefix length array move on one step and init the first values as -1.

1
2
3
4
5
6
7
8
9
10
11
12
13
void GetNext(char* p,int next[])  
{
next[0] = -1;
int k = -1, = 0;
while (j < (p.length - 1)) {
//p[k]表示前缀,p[j]表示后缀
if (k == -1 || p[j] == p[k]) {
++j, ++k, next[j] = k;
} else {
k = next[k];
}
}
}
CATALOG
  1. 1. How to calc the next array.