|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
这两个算法可是弄了我好久的,终于搞明白了,出此贴温习下
- //Brute-Force算法
- int index(SqString s,SqString t) //目标串s,模式串t
- {
- int i = 0,j = 0; //指针下标i标志s串,指针下标j标志t串
- while(i < s.length && j < t.length) //当各自指针下标小于各自的串的长度时,则执行该循环体
- {
- if(s.data[i] == t.data[j]) //如相等则继续匹配下一个字符
- {
- i++; //主串和子串依次匹配下一个字符
- j++;
- }
- else //如果不相等主串、子串指针回溯重新开始下一次匹配
- {
- i = i - j + 1; //主串从下一个位置开始匹配
- j = 0; //子串从头开始匹配
- }
- }
- if(j >= t.length)
- return(i - t.length); //返回匹配的第一个字符的下标
- else
- return(-1); //模式匹配不成,返回-1
- }
- //总结:这个算法简单,易于理解,但效率不高,主要原因是:主串指针i在若干个字符序列比较相等后,若有一个字符比较不相等,仍需回溯(即i = i - j + 1)
- //该算法在最好的情况下的时间复杂度为O(m),即主串的前m个字符等于模式串的m个字符。在最坏的情况下的时间复杂度为O(nm)
- //KMP算法
- int KMPIndex(SqString s,SqString t)
- {
- int next[MaxSize],i = 0,j = 0;
- GetNext(t,next);
- while(i < s.length && j < t.length)
- {
- if(j == -1 || s.data[i] == t.data[j])
- {
- i++;
- j++; //i,j各增1
- }
- else j = next[j]; //i不变,j后退
- }
- if(j >= t.length)
- return(i - t.length);
- else
- return(-1);
- }
- //求next[]的值
- void GetNext(SqString t.int next[]) //对模式串t,求next[]值
- {
- int j,k;
- j = 0;k = -1;next[0] = -1;
- while(j < t.length - 1)
- {
- if(k == -1 || t.data[j] == t.data[k]) //k为-1或比较的字符相等时
- {
- j++;k++;
- next[j] = k;
- }
- else k = next[k];
- }
- }
- //说明:上述定义的next[]在某些情况下仍有缺陷,例如,设主串s为"aaabaaaab",模式串t为"aaaab"
- //修正后的求nextval数组的算法如下:
- void GetNextval(SqString t,int nextval[])
- {
- int j = 0,k = -1;
- nextval[0] = -1;
- while(j < t.length)
- {
- if(k == -1 || t.data[j] == t.data[k])
- {
- if(t.data[j]!=t.data[k])
- nextval[j] = k;
- else
- nextval[j] = nextval[k];
- }
- else
- k = nextval[k];
- }
- }
- //修正后的KMP算法如下:
- int KMPIndex(SqString s,SqString t)
- {
- int nextval[MaxSize],i = 0,j = 0;
- GetNextval(t,nextval);
- while(i < s.length && j < t.length)
- {
- if(j == -1 || s.data[i] == t.data[j])
- {
- i++;
- j++;
- }
- else
- j = nextval[j];
- }
- if(j >= t.length)
- return(i - t.length);
- else
- return(-1);
- }
复制代码
|
评分
-
查看全部评分
|