字符串匹配
字符串匹配的形式化定义如下：假设文本是一个长度为
n的数组T[1...n]，而模式是一个长度为m的数组P[1...m]，其中m<=n。进一步假设P和T的元素都是来自一个有限字母集合M的字符。如M={0,1}或者M={a,b,c,...z}。
字符数组P和T通常称为字符串。
朴素字符串匹配算法
原理
朴素字符串匹配算法是通过一个循环找到所有的有效偏移，该循环对
n-m+1各可能的偏移值s进行检查，看是否满足条件P[1...m]=T[s+1,...s+m]。
步骤
- 对T，遍历其从
0~n-m的位置，在每一个位置上比较- 比较时，设当前偏移为
s,则比较T[s+1,s+2,...s+m]与P[1...m]。当二者每一个字符都相等时，则匹配- 将找到的有效偏移存入
std::vector中然后返回
性能
朴素字符串匹配算法的时间复杂度
O(m*n)
实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
template<typename IteratorT,typename IteratorP> std::vector<int> match(const IteratorT iterT_begin, const IteratorT iterT_end, const IteratorP iterP_begin, const IteratorP iterP_end) { typedef typename std::iterator_traits<IteratorT>::value_type T1; typedef typename std::iterator_traits<IteratorP>::value_type T2; static_assert(std::is_same<T1,T2>::value,"match error: sequence T and P must contain same type value"); auto lenT = std::distance(iterT_begin,iterT_end); auto lenP = std::distance(iterP_begin,iterP_end); if (lenT < 0) throw std::invalid_argument("match error: iterT_begin must <= iterT_end"); if (lenP < 0) throw std::invalid_argument("match error: iterP_begin must <= iterP_end"); std::vector<int> result; for(int i = 0;i < lenT-lenP; i++) { bool matched = true; for(int j = 0;j < lenP; j++) { if(*(iterT_begin+i+j) != *(iterP_begin+j)) { matched = false; break; } } if (matched) result.push_back(i); } return result; } |
本文为原创文章，版权归Aet所有，欢迎分享本文，转载请保留出处！
