PR值算法最近是否改动过?
发布网友
发布时间：2024-10-23 23:13
共1个回答
热心网友
时间：2024-11-04 04:25
不知道，拿分走人。/*************************************************************************
* Function Name:
* i = IndexKMP();
*
* Parameters:
* char *S - 主串或文本串
* char *P - 模式串
* int pos - 起始查询的位置
*
* Return Value:
* int
*
* Description:
* 一般的kmp算法实现模式匹配.
************************************************************************/
int IndexKMP(const char* S, const char* P, int pos)
{ // 利用模式串P的next函数求P在主串S中第pos个字符之后的位置的KMP算法
// 其中, P非空, 1≤pos≤strlen(S)
assert(S && P && "Primary String S or Pattern P is NULL in IndexKMP()!\n");
int i = pos - 1, j = 0; // 从第1个字符开始,i为主串的索引,j为模式串的索引
int n = strlen(S), m = strlen(P); // 取串长度
if (n < m) return 0; // 隐含条件:模式串的长度必须小于或等于主串的长度
assert((pos >= 1) && (pos <= n) &&
"Parameter pos is not in the domain[1, strlen] in IndexKMP()!\n");
int *next = NULL; // 生成next数组空间
next = (int*)malloc((m + 1) * sizeof(int)); // m+1是为了防止在get_next()函数中内存访问溢出
assert(next && "Allocate memory for next[] failed in IndexKMP()!\n!");
/* Preprocessing */
get_next(P, m, next); // 创建next数组___next数组访问越界
#ifdef _DEBUG
printf("\nNext[]:\n");
for (int x = 0; x < m; ++x)
{
printf("%d\t", next[x]);
}
printf("\n");
#endif
#ifdef _DEBUG
int iCount = 0;
#endif
/* Searching */
while (i <= n - m + j && j < m)
{
if (S[i] == P[j] || j == -1)
{ // 不失配继续比较后续字符
#ifdef _DEBUG
if (j != -1) iCount++;
#endif
++i;
++j;
}
else
{ // 模式串向右移动(特点：S的i指针不回溯，从P的k位置开始匹配)
#ifdef _DEBUG
iCount++;
#endif
j = next[j];
}
}
free(next); next = NULL;
if (j == m)
{
#ifdef _DEBUG
printf("匹配时KMP算法的比较次数为:");
PRi(iCount);
#endif
return (i - m + 1); // 匹配成功
}
else
{
#ifdef _DEBUG
printf("失配时KMP算法的比较次数为:");
PRi(iCount);
#endif
return 0; // 匹配不成功
}
} // IndexKMP
