本文共 2246 字,大约阅读时间需要 7 分钟。
halo~我是bay_Tong桐小白
本文内容是桐小白个人对所学知识进行的总结和分享,知识点会不定期进行编辑更新和完善,了解最近更新内容可参看更新日志,欢迎各位大神留言、指点
最近更新:
举例:在字符串"This is a simple example.“中匹配字符串"simple”
#include#include #define NotFound NULLtypedef char* Position;int main(){ char string[] = "This is a simple example."; char pattern[] = "simple"; Position p = strstr(string, pattern); if (p == NotFound) { printf("Not Found.\n"); } else { printf("%s\n", p); } return 0;}
测试结果如下
int BF(char* str, char* substr) { int i = 1, j = 1, k = i; if (strlen(str) < strlen(substr)) { return 0; } while (str[i] != '\0'&&substr[j] != '\0') { if (str[i] == substr[j]) { i++; j++; } else { j = 1; i = ++k; } } if (substr[j] == '\0') return k; else return 0;}
【暂时只总结求解方法,具体解释和原理后续更新】
数组下标为1和2的数组单元next值是一定的,分别为0和1
接下来数组单元的next值的求解,需要寻找这个字符之前的字符串中头部和尾部相等的长度最大的子串,这个子串的长度+1即为此字符的next值,如果这个字符之前的字符串头部和尾部没有可以匹配的子串,则此字符的next值为1例如此时数组下标为3字符b之前的字符串"aa",头部和尾部相同的长度最大的子串为“a”,长度为1,因此它的next值为1+1=2
数组下标为4的字符a之前的字符串"aab",头部和尾部没有可以匹配的子串,因此它的next值为1 数组下标为5的字符a之前的字符串"aaba",头部和尾部可以匹配的最大长度子串为“a”,因此它的next值为1+1=2 数组下标为6的字符c之前的字符串"aabaa",头部和尾部可以匹配的最大长度子串为“aa”,因此它的next值为1+2=3 【此处需注意,寻找字符串头部和尾部可以匹配的最大长度子串时,顺序需保持一致,如字符串"aabaa"头部和尾部长度为3的子串分别为"aab"与"baa",二者匹配不成功】nextval值需要根据next值求解,数组下标为1的字符nextval值是一定的,为0。
接下来数组单元的next值的求解,以它的next值为下标去访问数组单元,比较两个单元的字符是否相等,若相等则它们的nextval值也保持一致,若不相等,则此字符的nextval值与next值保持一致例如此时数组下标为2字符a的next值为1,将其作为数组下标对应的字符为a,两者相等,则nextval值也保持一致
数组下标为3字符b的next值为2,将其作为数组下标对应的字符为a,两者不相等,则它的nextval值与next值保持一致 依此继续进行求解,可完成全部求解持续更新中……
我是桐小白,一个摸爬滚打的计算机小白
转载地址:http://ubnqf.baihongyu.com/