这篇文章给大家分享的是有关C语言中实现朴素模式匹配算法的示例分析的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。
字符串模式匹配：在主串中找到与模式串相同的子串，并返回其所在位置。
注意：
①、子串——主串的一部分，一定存在。
②、模式串——不一定能在主串中找到
主串长度为n，模式串长度为m。
朴素模式匹配算法：将主串中所有长度为m的子串依次与模式串匹配对比，直到找到一个完全匹配的子串，或所有的子串都不匹配为止。
最多对比n-m+1个子串
（一）通过数组下标实现朴素模式匹配算法
若当前⼦串匹配失败，则主串指针 i 指向下⼀个⼦串的第⼀个位置，模式串指针 j 回到模式串的第⼀个位置
若 j > T.length，则当前⼦串匹配成功，返回当前⼦串第⼀个字符的位置 —— i - T.length
int Index(SString S, SString T){
int i=1,j=1;
while(i <= S.length && j<=T.length){
if(S.ch[i]==T.ch[j]){
++i;
++j; //继续比较后继字符
}
else{
i=i-j+2;
j=1; //指针后退重新开始匹配
}
}
if(j > T.length)
return i-T.length;
else
return 0;
}（二）时间复杂度
设主串⻓度为 n，模式串⻓度为 m，则
①、最坏时间复杂度 = O(nm)
②、最好时间复杂度 = O(n) 1. 最坏时间复杂度O(nm)
最坏的情况，每个⼦串都要对⽐ m 个字符，共 n-m+1 个⼦串，复杂度 = O((n-m+1)m) = O(nm)
注：很多时候，n >> m
2. 最好时间复杂度O(n)
最好的情况，每个⼦串的第⼀个字符就匹配失败，共 n-m+1 个⼦串，复杂度 = O(n-m+1) = O(n)
注：很多时候，n >> m
感谢各位的阅读！关于“C语言中实现朴素模式匹配算法的示例分析”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
