串的匹配运算

1、串的匹配运算 数 据 结 构串串的匹配运算串的匹配运算，就是判断某串是否是另一个已知串的子串，如是其子串，则给出该子串的起始点（即从已知串的哪个字符开始），故此运算又称为子串定位运算。设已知串r1和r2，要求判断r2是否是r1的子串，如果是其子串则给出起始点。显然r2是r1的子串的一个必要条件是，r2的长度Lr2一定要小于或等于r1的长度Lr1，即Lr2Lr1。假定串r1或r2都采用每结点存一个字符的链接存储结构。 串一种最简单的匹配算法首先将r2的第1个字符与r1的第1个字符比较，如二者匹配，则将r2的第二个字符与r1的第二个字符比较，这样比较下去，若直至r2的末尾一个字符都与r1的相应字符

2、匹配，则整个运算结束，返回子串的起始位置为1；当进行中遇到两串的相应字符不匹配时，则返回来将r2的第一个字符与r1的第二个比较，将r2的第二个字符与r1的第三个字符进行比较，若整个r2的各个字符都与r1的相应字符匹配，则运算结束，返回子串的起始位置为2； 串以此类推，如出现不匹配，再返回来将r2的第一个字符与r1的第三个字符比较。如此逐轮做下去，直至匹配成功，给出子串的起始位置或失败返回起始位置为0。例：r1=abafabcgw r2=abc 子串r2在r1中的起始位置为5。 串匹配算法int position ( linkstring *r1，*r2) linkstring *p，*p1，*

3、q，*q1; int i=0; p=r1; while(p!=NULL) /*循环扫描r1每结点*/ q=r2; while(q!=NULL) /*依次扫描r2每结点*/ if (p-ch=q-ch) /*是否与r1当前结点相等*/ /*相等，判定后面元素是否相同*/ p1=p-link; q1=q-link; while(p1-ch=q1-ch)串匹配算法续 p1=p1-link; q1=q1-link; if (q1=NULL) return i; /*返回子串起始位置*/ else q=q-link; p=p-link; i+; 串匹配算法分析与改进该匹配算法比较简单，但效率不高。算法的

4、时间复杂性为O(Lr1Lr2)。作两项改进，可以提高平均情况的运算速度: 1) 先检查r2的首尾两字符在r1中是否匹配，这两对字符都匹配了，再检查中间的字符； 2) 当后面一些轮r1中剩下的字符数已小于r2的长度时停止运算，因为这种情况匹配已不可能成功了。 返回串例4.1把顺序存储的两个串r1和r2首尾相连成一个串r，其中r1在前r2在后。解:在顺序存储结构中，实现串的连接操作，只要进行相应的“串复制”操作即可，只是如果在操作中出现两串长度之和大于上界maxlen时，做溢出处理。串例4.1算法void concat ( orderstring *r1, *r2, *r) int i; prin

5、tf(“r1=%s，r2=%sn”，r1-vec，r2-vec); if (r1-len+r2-lenmaxlen) printf(“上溢出n”); /*溢出处理*/ else for(i=1;ilen;i+) r-veci=r1-veci; /*将r1串传给r*/ for(i=1;ilen;i+) r-vecr1-len+i=r2-veci; /*r2传给r */ r-vecr1-len+i+1= 0； r-len=r1-len+r2-len; 串例4.2把两个以链接方式存储的串r1和r2首尾连成一个串r，其中r1在前，r2在后。linkstring *concat ( linkstring

6、 *r1, *r2) node *p，*q，*s,*r; r=(linkstring *)malloc(sizeof(linkstring); r-ch=r1-ch; q=r; p=r1-link; while(p!=NULL) 串例4.2算法续 s=(linkstring *)malloc(sizeof(linkstring); s-ch=p-ch; q-link=s; q=s; p=p-link;p=r2;while(p!=NULL) s=(linkstring *)malloc(sizeof(linkstring); 串例4.2算法续 s-ch=p-ch; q-link=s; q=s;

7、p=p-link; q-link=NULL; return (r); 串例4.3从链接存储的串r1中的第i个字符开始，把连续j个字符组成的子串赋给r。 linkstring *substring (linkstring *r1，int i，j) int k; linkstring *p， *q， *s， *r; p=r1; k=1; while(klink; k+; 串例4.3算法续if(p=NULL) printf(“出错n”);else r=(linkstring *) malloc(sizeof(linkstring); q=r; k=1; while(kch=p-ch; q-link=s; /