串的匹配運算

1、串的匹配運算 數(shù) 據(jù) 結(jié) 構(gòu)串串的匹配運算串的匹配運算，就是判斷某串是否是另一個已知串的子串，如是其子串，則給出該子串的起始點（即從已知串的哪個字符開始），故此運算又稱為子串定位運算。設(shè)已知串r1和r2，要求判斷r2是否是r1的子串，如果是其子串則給出起始點。顯然r2是r1的子串的一個必要條件是，r2的長度Lr2一定要小于或等于r1的長度Lr1，即Lr2Lr1。假定串r1或r2都采用每結(jié)點存一個字符的鏈接存儲結(jié)構(gòu)。 串一種最簡單的匹配算法首先將r2的第1個字符與r1的第1個字符比較，如二者匹配，則將r2的第二個字符與r1的第二個字符比較，這樣比較下去，若直至r2的末尾一個字符都與r1的相應(yīng)字符

2、匹配，則整個運算結(jié)束，返回子串的起始位置為1；當(dāng)進(jìn)行中遇到兩串的相應(yīng)字符不匹配時，則返回來將r2的第一個字符與r1的第二個比較，將r2的第二個字符與r1的第三個字符進(jìn)行比較，若整個r2的各個字符都與r1的相應(yīng)字符匹配，則運算結(jié)束，返回子串的起始位置為2； 串以此類推，如出現(xiàn)不匹配，再返回來將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) /*循環(huán)掃描r1每結(jié)點*/ q=r2; while(q!=NULL) /*依次掃描r2每結(jié)點*/ if (p-ch=q-ch) /*是否與r1當(dāng)前結(jié)點相等*/ /*相等，判定后面元素是否相同*/ p1=p-link; q1=q-link; while(p1-ch=q1-ch)串匹配算法續(xù) p1=p1-link; q1=q1-link; if (q1=NULL) return i; /*返回子串起始位置*/ else q=q-link; p=p-link; i+; 串匹配算法分析與改進(jìn)該匹配算法比較簡單，但效率不高。算法的

4、時間復(fù)雜性為O(Lr1Lr2)。作兩項改進(jìn)，可以提高平均情況的運算速度: 1) 先檢查r2的首尾兩字符在r1中是否匹配，這兩對字符都匹配了，再檢查中間的字符； 2) 當(dāng)后面一些輪r1中剩下的字符數(shù)已小于r2的長度時停止運算，因為這種情況匹配已不可能成功了。 返回串例4.1把順序存儲的兩個串r1和r2首尾相連成一個串r，其中r1在前r2在后。解:在順序存儲結(jié)構(gòu)中，實現(xiàn)串的連接操作，只要進(jìn)行相應(yīng)的“串復(fù)制”操作即可，只是如果在操作中出現(xiàn)兩串長度之和大于上界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算法續(xù) 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算法續(xù) s-ch=p-ch; q-link=s; q=s;

7、p=p-link; q-link=NULL; return (r); 串例4.3從鏈接存儲的串r1中的第i個字符開始，把連續(xù)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算法續(xù)if(p=NULL) printf(“出錯n”);else r=(linkstring *) malloc(sizeof(linkstring); q=r; k=1; while(kch=p-ch; q-link=s; /