串的模式匹配也称字串定位。设S和PAT分别为两个字符串,串的模式匹配就是以PAT为模式,查看字符串S中有无PAT这样的字串。若S中存在这样的字串,则给出其在S中首次出现的位置;否则给出0。
方法如下:先测试PAT的末尾字符与S中相对应位置的字符是否相同,若不相同,则将PAT的末尾字符和S的下一个字符比较,直到相同;然后再从PAT的第一个字符开始与S中对应位置的字符比较。当PAT的每一个字符与S中一个连续的字符序列对应相同时,则匹配成功。
活动指针p及q初始时指向PAT的第一个字符,然后经过移动,把q移动到PAT的最后那个字符处。指针r初始时指向S的第1个字符,然后根据PAT的长度(长度统计在变量n中)将指针t移动到S的第n个字符处,接着进行上述的比较过程。
算法描述如下:
typedef struct node{ char data; struct node *link; }*StrLink; int index(StrLink S, StrLink PAT){ StrLink p, q, r, t, save; /* q,t分别指向模式串PAT的最后一个元素和S中相对应位置的元素 */ int n, k, i = 0; /* n用于计数模式串PAT的元素个数 */ if( S == NULL || PAT == NULL ){ return 0; } q = PAT; n = 1; while( q->link != NULL ){ /* 将q指向模式串的最后一个元素并统计PAT的长度 */ q = q->link; n++; } t = S; save = S; /* save用于保留下一次重新比较的起始位置 */ for( k = 1; k < n; k++ ){ /* 将t移动到S的第n个字符处 */ t = t->link; } while( t != NULL ){ p = PAT; /* 重置p,r的值 */ r = save; i++; if( q->data == t->data ){ while( p != q && p->data == r->data ){ p = p->link; r = r->link; } if( p == q && p->data = r->data ) return i; /* 匹配成功,返回位置i */ } save = save->link; /* 移动到下一个匹配点 */ t = t->link; } return 0; }