求子串: bool SubString(SString &Sub,SString S, int pos, int len)
串的比较:int StrCompare(SString S, SString T)
求串在主串中的位置:int Index(sString S, SString T)
串的模式匹配
朴素模式匹配算法
原理:暴力破解
算法思想
主串长度n,模式串长度m
将主串中所有长度为m的子串与模式串比对
找到第一个与模式串匹配的子串,并返回子串起始位置
若所有子串都不匹配,则返回0
最坏时间复杂度=O(nm)
KMP算法
不匹配的字符之前,一定是和模式串一致的
依赖于模式串,与主串没有关系
主要优点:主串指针不回溯
用一个next数组存储模式串指针
算法思想
根据模式串T,求出next数组
利用next数组进行匹配(主串指针不回溯)
对于每模式串 t 的每个元素 t j,都存在一个实数 k ,使得模式串 t 开头的 k 个字符(t 0 t 1…t k-1)依次与 t j 前面的 k(t j-k t j-k+1…t j-1,这里第一个字符 t j-k 最多从 t 1 开始,所以 k < j)个字符相同。如果这样的 k 有多个,则取最大的一个。模式串 t 中每个位置 j 的字符都有这种信息,采用 next 数组表示,即 next[ j ]=MAX{ k }