网站如何做关键词大型html5浅蓝色网站设计公司dede模板

当前位置： 首页 > news >正文

网站如何做关键词,大型html5浅蓝色网站设计公司dede模板,淘宝客静态网站,ui设计培训大概多少钱串 1. 定义2. 串的比较3. 串的存储结构4. 具体实现5. 模式匹配5.1 常规思路实现5.2 KMP模式匹配算法5.2.1 next数组计算5.2.1 代码计算next数组5.2.2 KMP算法实现 1. 定义 串(string)是由零个或多个字符组成的有限序列#xff0c;又叫字符串。 一般记为s a 1 , a 2 , … ,… 串 1. 定义2. 串的比较3. 串的存储结构4. 具体实现5. 模式匹配5.1 常规思路实现5.2 KMP模式匹配算法5.2.1 next数组计算5.2.1 代码计算next数组5.2.2 KMP算法实现 1. 定义 串(string)是由零个或多个字符组成的有限序列又叫字符串。 一般记为s a 1 , a 2 , … , a n , ( n ≥ 0 ) a_1,a_2,…,a_n,(n\ge0) a1​,a2​,…,an​,(n≥0)。串中字符数目n称为串的长度。零个字符的串称为空串。

1. 串的比较 给定两个串s a 1 , a 2 , … , a n a_1,a_2,…,a_n a1​,a2​,…,an​t b 1 , b 2 , … , b m b_1,b_2,…,b_m b1​,b2​,…,bm​当满足以下条件之一时 s t st st (1) n m nm nm且 a i b i a_ib_i ai​bi​例如 s h a p , t h a p p y shap,thappy shap,thappy就有 s t st st。 (2)存在某个 k ≤ min ⁡ ( m , n ) k\le\min(m,n) k≤min(m,n)使得 a i b i a_ib_i ai​bi​ a k b k a_kb_k ak​bk​就有 s t st st。例如 s h a p p e n shappen shappen t h a p p y thappy thappy此时 k 4 k4 k4且字符有 e y ey ey则 s t st st。
2. 串的存储结构 串的存储结构与线性表相同分为两种顺序存储结构和链式存储结构。 串的顺序存储结构使用一组地址连续的存储单元来存储传中的字符序列。串的链式存储结构与线性表相似但是如果一个字符占用一个结点就会存在很大的空间浪费。 串的链式存储结构除了在连接串与串操作时有一定方便之外总的来说不如顺序存储灵活性能也不如顺序存储结构好。 对于串的顺序存储有一些变化串值的存储空间可在程序执行过程中动态分配而得。
3. 具体实现 为了方便管理利用C的类实现了String #include iostream using namespace std;class String {friend ostream operator(ostream os, const String s); // 友元函数 private:int max_size 10;int extend_size 10;char* ptr; // 字符指针int len;// 扩展内存void ExtendString(){char* new_ptr new char[max_size extend_size];memset(new_ptr, 0, sizeof(char) * (max_size extend_size));// 拷贝数据memcpy(new_ptr, ptr, sizeof(char) * max_size);// 清空内存delete[] ptr;// 指向新内存ptr new_ptr;// 更新最长大小max_size max_size extend_size;}public:String() // 构造函数{// cout 调用了默认构造函数 endl;ptr new char[max_size]; // 初始化内存memset(ptr, 0, sizeof(char) * max_size);len 0; // 字符串长度}String(const char* s) // 构造函数{cout 调用了构造函数 endl;int len strlen(s);ptr new char[this-max_size]; // 初始化内存memset(ptr, 0, sizeof(char) * this-max_size);while (this-max_size len){ExtendString();}// 拷贝数据memcpy(this-ptr, s, sizeof(char) * len);this-len len;}String(const String s) // 构造函数{cout 调用了拷贝构造函数 endl;ptr new char[s.max_size]; // 初始化内存memset(ptr, 0, sizeof(char) * s.max_size);// 拷贝数据memcpy(ptr, s.ptr, sizeof(char) * s.len); // 拷贝字符串len s.len;max_size s.max_size;}String operator(const char* str) // 赋值函数{cout 调用了重载的赋值函数char* endl;int len strlen(str);while (strlen(str) this-max_size){ExtendString();}memcpy(this-ptr, str, sizeof(char) * len);this-len len;return *this;}String operator(const String str) // 赋值函数{cout 调用了重载的赋值函数String endl;while (str.max_size this-max_size){ExtendString();}memcpy(this-ptr, str.ptr, sizeof(char) * str.len);this-len str.len;return *this;}// 清空字符串void clear() {memset(ptr, 0, sizeof(char)*max_size); // 内存置0len 0;}// 返回字符串长度int length()const {return len; }// 返回从第pos个字符开始长度为len的子串String sub(int pos, int len) {// 创建临时对象String tmp;for (int i 0; i len; i){tmp.ptr[i] this-ptr[i pos - 1];}tmp.len len;return tmp;}// 将str插入到当前字符第pos个字符之后String Insert(int pos, const String str){int whole_len str.len this-len;while (this-max_size whole_len){ExtendString();}// 插入字符// 1.保存第pos个字符之后的所有字符后移str_len位 即pos-1开始的len-pos个字符移动到posstr_len-1for (int i this-len; i pos; i–){this-ptr[i str.len - 1] this-ptr[i - 1]; // }// 2.插入字符从 str.ptr[0]到 str.ptr[len-1] 到pos-1至posstr.len-1;memcpy((this-ptr[pos]), (str.ptr[0]), sizeof(char) * str.len);this-len whole_len;return *this;}~String(){delete[] ptr;ptr nullptr;len 0;}bool operator(const String str)const{int i 0;for (i 0; i this-len i str.len; i){if (this-ptr[i] str.ptr[i]){continue;}if (this-ptr[i] str.ptr[i]) // 前面都相等一旦有一个字符大则整个字符串都大{return false;}else // 前面都相等当前字符小{return true;}}if (this-len str.len)// 退出比较的原因是前面字符都相等但当前字符串的字符较短{return true;}return false;}bool operator(const String str)const{int i 0;for (i 0; i this-len i str.len; i){if (this-ptr[i] str.ptr[i]){continue;}if (this-ptr[i] str.ptr[i]) // 前面都相等一旦有一个字符小则整个字符串都小{return false;}else // 前面都相等当前字符大{return true;}}if (this-len str.len)// 退出比较的原因是前面字符都相等但当前字符串的字符更长{return true;}return false;} };// 重载输出 ostream operator(ostream os, const String s) {for (int i 0; i s.len; i){os s.ptr[i];};return os; }int main(void) {String s1;s1 ace;String s2 s1;String s3(bdf);String s4 asw; // 自动类型转换调用赋值函数/s3 s2.sub(1, 2);/cout s1 endl;s1.clear();cout s1 endl;cout s2 endl;cout s3 endl;cout ( s3 s2) endl;s2.Insert(3, s3);cout s2 endl;return 0; }5. 模式匹配 在一段字符串中去定位子串的位置的操作称作串的模式匹配这是串中最重要的操作之一。 假设我们要从主串Sgoodgoogle中找到子串Tgoogle的位置。通常需要进行下面的步骤 主串S第一位开始S与T的前三个字符都匹配成功但S的第四个字符为d而T的第四个字符为g。第一位匹配失败。主串S第二位开始S首字符为o而T的首字符为g第二位匹配失败。同理第三位和第四位都匹配失败主串第五位开始S与T6个字母全匹配匹配成功。 简单来说对主串的每个字符作为子串开头与要匹配的子串进行匹配。对主串做外部循环每个字符开头做子串T长度的内部循环直到匹配成功或主串遍历完成为止。 5.1 常规思路实现 int Index(const String T){int i, j 0;for (i 0; i this-len; i){for (j 0; j T.len; j){if (this-ptr[ij] T.ptr[j]) // 主串以i开头的T长度的子串匹配{continue;}break;}if (j T.len) // 子串匹配成功{return i; // 返回此时子串在主串中的位置}}return -1; // 匹配失败}5.2 KMP模式匹配算法 常规思路的匹配算法需要挨个遍历主串和子串效率低效。KMP算法的思路是当发现某一个字符不匹配的时候由于已经知道之前遍历过的字符利用这些信息避免暴力算法中回退的步骤。 KMP算法的原理 1在匹配过程中主串的指针不需要回溯只回溯子串的指针。 2如果子串和主串中前n个字符匹配成功遇到匹配失败的字符时子串回溯的下标由子串的内容决定回溯到匹配失败前子串内容最长相等前后缀 的长度然后继续比较。 前缀包含首位字符但不包含末位字符的子串。如ababa的前缀包括aababaabab 后缀包含末位字符但不包含首位字符的子串。如ababa的后缀包括abaabababa。 则对于字符串:ababa最长公共前后缀为aba。 具体流程依次匹配主串和子串的字符当遇到子串与主串字符不匹配时子串指针回溯并从回溯的位置继续与主串当前位置字符比较。如图中所示ABABABCAA与ABABC匹配当遇到主串字符A时子串字符为C此时无法匹配子串指针回溯到第3个字符即A处继续比较。KMP算法的关键是如何获取子串回溯位置即next数组。
   5.2.1 next数组计算 对于子串ABABC 第一个字符A没有前缀没有后缀对应的next数组值为0。 第二个字符AB包含的前后缀有A B 对应的next数组值为1。 第三个字符的子串为ABA包含的前后缀有A A AB BA 最长的长度为1。则next数组值为1。 第四个字符的子串为ABAB包含的前后缀有A B AB AB ABA BAB最长的公共前后缀长度为2。next数组值为2。 第五个字符的子串为ABABC包含的前后缀有A C AB BC ABA ABC ABABA BABC最长的公共前后缀长度为0。next数组值为0。 因此对于ABABC的next数组值为01120。 对于子串AABAAF计算next数组 初始化i 和 j 其中i指向的是后缀末尾j指向的是前缀末尾即把S[0,j]看作是子串把S[1,i]看作是主串来理解。初始时j0i1next[0]0。 前后缀不同的情况S[i]!S[j]此时需要查询next[j-1]的值查询到j需要回退的位置必须要满足j0直到 S[i]S[j]或者回退到初始位置。 前后缀相同的情况S[i]S[j]j。 更新next数组next[i]j。 模拟运行 初始化next[0] 0. i 1 ,j 0.i1,j0.S[0]AS[1]A jj1. next[1]1.i2,j1;S[1]A ! S[2] B jnext[j-1]next[0]0 S[0]!S[2] j0. next[2] 0.i3,j0;S[0] A S[3]A jj1. next[3] 1.i4,j1;S[1]A S[4] A jj2. next[4] 2.i5,j2;S[2]B!S[5]F j next[j-1]next[1] 1 S[1]!S[5] jnext[j-1]next[0]0 j0.next[5]0.
   5.2.1 代码计算next数组 // 获取next数组int* getNext(){// 创建next数组长度与字符串长度一致delete[] next;next new int[this-len];memset(next, 0, sizeof(int) * this-len);// 初始化int i, j 0;next[0] 0;for (i 1; i this-len; i){// 前后缀不相同的情况while (j 0 ptr[i] ! ptr[j]){// 回溯jj next[j - 1];}// 前后缀相同的情况if (ptr[i] ptr[j]){j;}// 更新nextnext[i] j;}return next;}5.2.2 KMP算法实现 / KMP算法int KMP(String T){// 获取子串next数组int* next_ptr T.getNext();// 开始匹配int i 0, j 0;while (i len){if (ptr[i] T.ptr[j]) // 匹配成功{i; j;}else if (j 0) // 匹配失败子串指针回溯并且需要保证回溯位置不越界即无法回溯到首个字符前{j next_ptr[j - 1];}else // 子串第一个字符就匹配失败i;if (j T.len)// 子串已经到达末尾即全部匹配上{return i - j; // 返回位置}}return -1; // 匹配失败}