[数据结构与算法]数据结构——串

串

• 串（string）是由零个或多个字符组成的有限序列，又叫字符串

串的存储结构——元素为 char 的线性表的拓展

• 线性存储结构
• 链式存储结构

朴素的模式匹配算法

/* 返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数返回值为0。 */
/* 其中,T非空,1≤pos≤StrLength(S)。 */
int Index(char *S, char *Substring, int pos)
{
    int SubCursor = 1;
    while (pos <= S[0] && SubCursor <= Substring[0])
    {
        if (S[pos] == Substring[SubCursor])
        {
            pos++;
            SubCursor++;
        }
        else
        {
            pos = pos - SubCursor + 2;
            SubCursor = 1;
        }
    }
    if (SubCursor == Substring[0] + 1)
        return pos - SubCursor + 1;
    else
        return 0;
}

• 最好的情况：每次都是第一个字母就不匹配
• 每次都是子串最后一个字母不匹配，造成子串之前的匹配“前功尽弃”
• 改进：KMP 模式匹配算法

磨刀不误砍柴工 —— KMP 模式匹配算法

• 核心思想：若在字串中有与前缀相等的字符，就可以省略不必要的重复判断
• 在朴素模式的匹配算法中，主串的 i 值是通过不断地回溯来完成的，而 KMP 模式匹配算法就是为了让这不必要的回溯不在发生
• SubCursor 值的变化与主串其实没有什么关系，关键就取决于 Substring 的结构中是否有首尾重复
• KMP 算法仅当模式与主串之间存在许多“部分匹配”的情况下才体现出它的优势，否则两者差异并不明显

KMP 模式匹配算法的改进

//预处理
void get_nextval(String T, int* next)
{
	int main_cursor = 1, sub_cursor = 0;
	next[1] = 0; // flag！！！表示无法使用 KMP 模式匹配算法，
	//将按照朴素匹配算法进行下一位的匹配
	while (main_cursor < T[0])
	{
		if (sub_cursor == 0 || T[sub_cursor] == T[main_cursor]) // sub_cursor == 0，特判完全不相等,无法利用 KMP 算法的情况，并**推进**
		{
			main_cursor++;
			sub_cursor++;
			if (T[sub_cursor] == T[main_cursor])
				next[main_cursor] = next[sub_cursor]; //若T[sub_cursor] == T[main_cursor]
													  //在下一次进行的比较中，主串的“比较位”必定也不同于新来的字串末尾
													  //该比较无意义
													  // next[main_cursor] = next[sub_cursor] ——其值等于最长的那个后缀不等于 T[main_cursor]，
													  //且前缀相同的“有效偏移量”
			else
				next[main_cursor] = sub_cursor;
		}
		else
			sub_cursor = next[sub_cursor]; //从某种意义上来看，
												  //寻求 next 数组即是在将字符串 T 首部和 sub_cursor 尾部进行匹配
												  //因此，在匹配过程中可以利用之前已计算好的 next 数组
	}
}

int Index_KMP_improved(String main_string, String sub_string, int pos)
{
	int sub_cursor = 1;
	int* next = (int*)malloc(sizeof(int) * (main_string[0] + 1));
	get_nextval(sub_string, next);
	while (sub_cursor <= sub_string[0] && pos <= main_string[0])
	{
		if (sub_cursor == 0 || main_string[pos] == sub_string[sub_cursor]) // sub_cursor==0 ——> 用于
																		   //特判子串与主串之间从第一个元素开始就完全不相等的特例 ——> 即其没有“有效前缀”，无法使用 KMP 匹配算法，
																		   // nextval = 0 是一种类似于 flag 的存在，即表示放弃使用 KMP 算法，
																		   //直接使用类似于朴素匹配算法的方法，并利用原来的“偏移设置程序”，将字串k设置为1，
																		   //将主串i前进一位，继续进行比较
		{
			sub_cursor++;
			pos++;
		}
		else
			sub_cursor = next[sub_cursor]; // sub_cursor **退回** 合适的位置，pos 位置不变
	}
	if (sub_cursor == sub_string[0] + 1)
		return pos - sub_cursor + 1;
	return ERROR;
}