例1、求子串 上述串的操作是最基本的,其中后四个还有变种形式: strncpy, strncat, strncmp, stench.。串的其余操作可由 这些基本操作组合而成。 例1、求子串求子串的过程即为复制字符序列的过程,将串 s中的第pos个字符开始长度为len的字符复制到串T中。 o void substr(string sub, string s, int pos, int len)t ●if(pos0‖!pos> strlen(s)-1l|en<0) error("parameter error o strncpy(sub, &sipos], len); 3 北京邮电大学自动化学院 16
北京邮电大学自动化学院 16 ⚫ 上述串的操作是最基本的，其中后四个还有变种形式： strncpy，strncat，strncmp，strnchr。串的其余操作可由 这些基本操作组合而成。 例1、求子串 ⚫ 例1、求子串 求子串的过程即为复制字符序列的过程，将串 S中的第pos个字符开始长度为len的字符复制到串T中。 ⚫ void substr(string sub,string s,int pos,int len) { ⚫ if(pos<0 || pos>strlen(s)-1 || len<0) ⚫ error(“parameter error”) ⚫ strncpy(sub,&s[pos],len); }
例2、串的定位 ●例2、可利用串比较、求串长和求子串等操作实现定位函数 ndex(S,T,pos)串的定位。 ●ndex(s,T,pos) 初始条件:串S和T存在,T是非空串, 1 possStrLength(s)。 操作结果:若主串S中第pos个字符之后存在和串T值相同 的子串,则返回它在主串S中第pos个字符之后第一次出现 的位置;否则函数值为0。 北京邮电大学自动化学院
北京邮电大学自动化学院 17 ⚫ 例2、可利用串比较、求串长和求子串等操作实现定位函数 Index( S, T, pos )串的定位。 例2、串的定位 ⚫ Index (S, T, pos) ⚫ 初始条件：串S和T存在，T是非空串， 1≤pos≤StrLength(S)。 ⚫ 操作结果： 若主串 S 中第pos个字符之后存在和串 T 值相同 的子串， 则返回它在主串 S 中第pos个字符之后第一次出现 的位置；否则函数值为0
例2、串的定位 ●“子串在主串中的位置”是指子串中的第一个字 符在主串中的位序。 假设S=" abcaabcaaabc",T="bca oIndex(s,T, 1)=2, oIndex s, T, 3)=6; oIndex(, T,8=0 北京邮电大学自动化学院
北京邮电大学自动化学院 18 ⚫ “子串在主串中的位置”是指子串中的第一个字 符在主串中的位序。 例2、串的定位 ⚫假设 S = abcaabcaaabc , T = bca ⚫Index(S, T, 1) = 2; ⚫Index(S, T, 3) = 6; ⚫Index(S, T, 8) = 0;
例2、串的定位 算法的基本思想为: StrCompare( SubString(S, i, StrLength(D), T)2-0 S串 pos T 串 n-m+1T串 北京邮电大学自动化学院 19
北京邮电大学自动化学院 19 算法的基本思想为： StrCompare(SubString(S, i, StrLength(T)), T ) S 串 T 串 T 串 i pos n-m+1 ? 0 例2、串的定位
o int Index(String S, String T, int pos)i ∥T为非空串。若主串S中第pos个字符之后存在与T相等的子串 ●∥则返回第一个这样的子串在S中的位置,否则返回0 o If (pos>0)i n= StrEngth(s); m= StrEngth T);i= pos; ●Whle(i<=nm+1){ e SubString(sub, S, i, m); if StrCompare(sub, T)l=0)++i; ● else return i;}∥ whille }∥if return0;∥S中不存在与T相等的子串 }∥ndex 北京邮电大学自动化学院
北京邮电大学自动化学院 20 ⚫ int Index (String S, String T, int pos) { ⚫ // T为非空串。若主串S中第pos个字符之后存在与 T相等的子串， ⚫ // 则返回第一个这样的子串在S中的 位置，否则返回0 ⚫ If (pos>0) { n = StrLength(S); m = StrLength(T); i = pos; ⚫ while ( i <= n-m+1) { ⚫ SubString (sub, S, i, m); ⚫ return 0; // S中不存在与T相等的子串 ⚫ } // Index ⚫ if (StrCompare(sub，T) != 0) ++i ; ⚫ else return i ; } // while } // if