参考答案看底部
1.求改进的失败函数nextval[j]
题目描述
在KMP算法中，进行模式匹配，在匹配失败时，主串的位置i不回溯，模式串需要根据改进的失败函数nextval[j]的值，j转移到nextval[j]位置继续进行比较。试设计函数求模式串的改进的失败函数nextval[j]。
输入描述
输入模式串
输出描述
输出模式串的改进的失败函数nextval[j]
样例输入
aaaaab
样例输出
-1-1-1-1-14
2. 求模式串的失败函数next[j]
题目描述
在KMP算法中，进行模式匹配，在匹配失败时，主串的位置i不回溯，模式串需要根据失败函数next[j]的值，j转移到next[j]位置继续进行比较。试设计函数求模式串的next[j]。
输入描述
输入模式串。
输出描述
输出模式串的失败函数。
样例输入
abcabcaabbc
样例输出
-10001234120
3. 数据结构【稀疏矩阵】三元组表示的稀疏矩阵的快速转置
题目描述
编写函数实现三元组表示的稀疏矩阵的快速转置
前置代码：
//算法4.3 三元组表示的稀疏矩阵的快速转置
#include
using namespace std;
#define MaxSize 100
typedef int ElemType;
//三元组结构体
typedef struct
{
int row,col; //行、列
ElemType value; //值
}Triple;
//稀疏矩阵的三元组表示
