成都鱼羊环保网站制作设计,音乐网站开发可行性分析,县直门户网站建设管理,宿迁宿城区屠园乡网站建设KMP算法与BF算法不一样的在于#xff0c;当主串与子串不匹配时#xff0c;主串不回溯#xff0c;选择了子串回溯#xff0c;大大提高了运算效率。 借用了next1【】数组#xff0c;让子串回溯。get_next函数求next1【】数组#xff0c;get_next函数的实现难点在于下列几行… KMP算法与BF算法不一样的在于当主串与子串不匹配时主串不回溯选择了子串回溯大大提高了运算效率。 借用了next1【】数组让子串回溯。get_next函数求next1【】数组get_next函数的实现难点在于下列几行代码 while (i T.length) { if (j 0 || T.ch[i] T.ch[j]) { i j; next1[i] j; } else j next1[j]; } 只要明确两点就容易理解
1、Tj Tnext[j]那么next[j1]的最大值为next[j]1。
2、Tj ! Tnext[j]那么next[j1]可能的次最大值为next[ next[j] ]1,以此类推即可求出next[j1]。
#includeiostream
#includestring
using namespace std;
int next1[1000];
typedef struct node
{char ch[251];int length0;//串当前长度
}SString;
void get_next(SString T)
{int i 1;//当前串正在匹配字符串位置也是next数组的索引next1[1] 0;int j 0;while (i T.length){if (j 0 || T.ch[i] T.ch[j]){i;j;next1[i] j;}elsej next1[j];}
}
int Index_KMP(SString S, SString T, int pos)//S主串T子串pos从主串pos位置开始匹配
{int i pos, j 1;//i为主串下标j为子串下标while (i S.length j T.length){if (S.ch[i] T.ch[j])//匹配往下继续{i;j;}elsejnext1[j];}if (j T.length) return i - T.length;//返回主串与子串匹配时主串的第一个下标else return 0;
}
int main()
{SString s;SString t;cout 输入主串长度 ;cin s.length;cout endl;cout 输入子串长度;cin t.length;cout endl 输入主串;for (int i 1; i s.length; i)//从下标1开始储存{cin s.ch[i];}cout endl 输入子串;for (int i 1; i t.length; i){cin t.ch[i];}get_next(t);int a Index_KMP(s, t, 1);cout endl a;
}
