KMP算法
KMP_Pre
/*
* next[]的含义，x[i - next[i]...i - 1] = x[0...next[i] - 1]
* next[i]为满足x[i - z...i - 1] = x[0...z - 1]的最大z值（就是x的自身匹配）
*/
void KMP_Pre(char x[], int m, int next[])
{
int i, j;
j = next[0] = -1;
i = 0;
while (i < m)
{
while (-1 != j && x[i] != x[j])
{
j = next[j];
}
next[++i] = ++j;
}
return ;
}
preKMP
/*
* kmpNext[]的意思：next'[i] = next[next[...[next[i]]]]
* （直到next'[i] < 0或者x[next'[i]] != x[i]）
* 这样的预处理可以快一些
*/
void preKMP(char x[], int m, int kmpNext[])
{
int i, j;
j = kmpNext[0] = -1;
i = 0;
while (i < m)
{
while (-1 != j && x[i] != x[j])
{
j = kmpNext[j];
}
if (x[++i] == x[++j])
{
kmpNext[i] = kmpNext[j];
}
else
{
kmpNext[i] = j;
}
}
return ;
}
KMP_Count
/*
* 此函数与上述两个函数中的任意一个搭配使用（即调用上述两个函数中的任意一个）
* 返回x在y中出现的次数，可以重叠
*/
int next[10010];
int KMP_Count(char x[], int m, char y[], int n)
{
// x是模式串，y是主串
int i, j;
int ans = 0;
// preKMP(x, m, next);
KMP_Pre(x, m, next);
i = j = 0;
while (i < n)
{
while (-1 != j && y[i] != x[j])
{
j = next[j];
}
i++, j++;
if (j >= m)
{
ans++;
j = next[j];
}
}
return ans;
}
扩展KMP
*
* 扩展KMP
* next[i]:x[i...m-1]的最长公共前缀
* extend[i]:y[i...n-1]与x[0...m-1]的最长公共前缀
*/
void preEKMP(char x[], int m, int next[])
{
next[0] = m;
int j = 0;
while (j + 1 < m && x[j] == x[j + 1])
{
j++;
}
next[1] = j;
int k = 1;
for (int i = 2; i < m; i++)
{
int p = next[k] + k - 1;
int L = next[i - k];
if (i + L < p + 1)
{
next[i] = L;
}
else
{
j = std::max(0, p - i + 1);
while (i + j < m && x[i + j] == x[j])
{
j++;
}
next[i] = j;
k = i;
}
}
return ;
}
void EKMP(char x[], int m, char y[], int n, int next[], int extend[])
{
preEKMP(x, m, next);
int j = 0;
while (j < n && j < m && x[j] == y[j])
{
j++;
}
extend[0] = j;
int k = 0;
for (int i = 1; i < n; i++)
{
int p = extend[k] + k - 1;
int L = next[i - k];
if (i + L < p + 1)
{
extend[i] = L;
}
else
{
j = std::max(0, p - i + 1);
while (i + j < n && j < m && y[i + j] == x[j])
{
j++;
}
extend[i] = j;
k = i;
}
}
return ;
}
