1、串的长度：串中所含字符的个数 空串：长度为0 空格串：由多个空格字符构成的字符串

2、子串 定义：串中任意个连续的字符组成的子序列成为该串的子串 计算方法：ab的子串：a、b、ab和一个空子串共4个即（2+1+1）个，abc的子串：a、 b、 c、 ab、 bc 、abc和一个空子串 共（3+2+1+1）个， 所以若字符串的长度为n,则子串的个数就是[n*(n+1)/2]个， “software”中非空子串的个数就是8+7+….+1=36个。 3、KMP算法、BF算法 BF算法（普通匹配算法）：时间复杂度O(m*n)；看空间复杂度O(1) KMP算法：时间复杂度O(m+n)；空间复杂度O(n) 4、多型数据结构 多型：数据元素的类型不确定 栈：整数栈、字符栈、对象栈 字符串：字符 5、模式匹配 模式匹配是数据结构中字符串的一种基本运算，给定一个子串，要求在某个字符串中找出与该子串相同的所有子串，这就是模式匹配 6、广义表与字符串 广义表L=(A,B,C),表头是A，表尾是（B,C)，这是定义。 tail()表示取字符串的尾部，head()表示取字符串的头，concat()表示字符串拼接。 取两次尾部一次头部，然后合并 7、把字符串“abcd”倒序“dcba”

查找字符串： 函数fun的功能是:从形参ss所指字符串数组中,查找含有形参substr所指子串的所有字符串，并输出，若没找到则输出相应信息。Ss所指字符串数组中共有N个内容不同的字符串,且串长小于M。 程序中库函数strstr（s1,s2）的功能室在s1串中查找s2子串，若没有，函数值为0;若有，函数值为非0。 请在程序的下画线处填入正确的内容并将下画线删除，使程序得出正确的结果。 试题程序。

define N 5

define M 15

void fun(char (*ss)[M], char *substr) { int i, find = 0; /*****found*****/ for (i = 0; i < N); i++) /*****found*****/ if ( strstr(ss[i], substr )) != NULL ) { find = 1; puts(ss[i]); printf(“/n”); } /*****found*****/ if (find == 0 ) printf(“/nDon’t found!/n”); } void main( ) { char x[N][M] = {“BASIC”, “C langwage”, “java”, “QBASIC”, “access”}, str[M]; int i; printf(“/nThe original string/n/n”); for (i = 0; i < N; i++) puts(x[i]); printf(“/n”); printf(“/nEnter a string for search : “); gets(str); fun(x, str); }