文档介绍：字符串字符串((StringString))字符串是字符串是n ( n ( ?? 0 ) 0 ) 个字符的有限序列,记个字符的有限序列,记作作S : S : ““22……ccn-1n-1””其中,其中,SS是串名字是串名字““22……ccn-1n-1””ii是串中字符是串中字符nn是串的长度。是串的长度。如:如:““e to Shanghai !!!e to Shanghai !!!””在计算机非数值计算应用中,经常遇到字符序列的处在计算机非数值计算应用中,经常遇到字符序列的处理。如,文字编辑、情报检索、自然语言翻译、事务理。如,文字编辑、情报检索、自然语言翻译、事务处理、图象处理等应用中经常遇到的那样。在计算机处理、图象处理等应用中经常遇到的那样。在计算机中,一个字符集上的每个字符用定长的代码表示,所中,一个字符集上的每个字符用定长的代码表示,所有可能的各种字符都可以对应一个确定的代码。一个有可能的各种字符都可以对应一个确定的代码。一个特定的字符序列称为字符串,简称为串。有两种方法特定的字符序列称为字符串,简称为串。有两种方法能比较方便地表示一个字符串。一是人为地约定一个能比较方便地表示一个字符串。一是人为地约定一个特殊的代码为字符序列的结束符,每个字符串最后都特殊的代码为字符序列的结束符,每个字符串最后都有这个结束符。二是,为每个字符序列另引入一个整有这个结束符。二是,为每个字符序列另引入一个整数,让该整数指出该字符串的字符个数。本书采用第数,让该整数指出该字符串的字符个数。本书采用第一种表示字符串的方法一种表示字符串的方法模式匹配是串的基本运算之一。有两个字符串T和S,字符串T称为正文,字符串S称为模式,要求找出模式S在正文T中的首次出现的位置。一旦模式S在正文T中找到,就说发生一次匹配。有些应用可能会要求找出所有的匹配位置。串的模式匹配串的模式匹配nn定义定义在串中寻找子串(第一个字在串中寻找子串(第一个字符)在串中的位置符)在串中的位置nn词汇词汇在模式匹配中,子串称为在模式匹配中,子串称为模模式式,串称为,串称为目标目标。。nn示例示例目标目标T : T : ““BeijingBeijing””模式模式P : P : ““jinjin””匹配结果匹配结果= 3 = 3 记正文记正文TT的字符个数为的字符个数为nn,令,令T= tT= t00tt11tt22……ttn-1n-1,,记模式记模式SS的字符个数为的字符个数为mm,令,令S= sS= s00ss11ss22……ssm-1m-1。。若正文中自位置若正文中自位置kk开始有一次匹配,则有开始有一次匹配,则有ssjj = t = tk+jk+j,,0 <= j < m0 <= j < m。。并且对所有并且对所有p<kp<k,没有对所有的,没有对所有的0<=j<m0<=j<m,,mm个等式个等式ssjj = t = tp+jp+j全都成立。全都成立。 简单匹配简单匹配第第11趟趟TTa b b a b a a b b a b a 穷举的模式穷举的模式PPa b aa b a匹配过程匹配过程第第22趟趟TT a b b a b a a b b a b a P P a b a a b a第第33趟趟TT a b b a b a a b b a b a P P a b a a b a第第44趟趟TTa b b a b aa b b a b a P P a b aa b a?? char *stringSearch(char *t, char *p) { int n = strlen(t), m = strlen(p), i, j; for(j = 0; j <= n - m; j++) { /*从t[j]开始的子串与字符串p比较*/ for(i = 0; i < m && t[j+i] == p[i]; i++); if (i == m) return t+j; } return NULL; } 若不考虑正文至少有模式长的字串个数,且用若不考虑正文至少有模式长的字串个数,且用字符指针编写,可简写成以下形式。字符指针编写,可简写成以下形式。char char **stringSearch(char stringSearch(char **t, char t, char **s)s){ char { char **q, q, **p; p; for(; for(; **t !