kmpsearch.cpp

一个我的数据结构解题集合

#include <string>
#include "Vector.h"
#include "KMPSearch.h"
using namespace std;

namespace {

	/* 求模式串ptn的next数组, 
	 * 结果填入next
	 * 扩展: next[ptn.size()] 为模式完全匹配时匹配下一模式的模式串偏移量
	 */
	void getnext(const string& ptn, Vector<int>& next) {
		next.enlarge(ptn.size()+1);
		int i = 0, j = -1;
		next[0] = j;
		while ( i < ptn.size()-1 ) {
			if ( j == -1 || ptn[i] == ptn[j] ) {
				++i; ++j;
				if (ptn[i] != ptn[j]) {
					next[i] = j;
				} else {
					next[i] = next[j];
				}
			} else {
				j = next[j];
			}
		}
		next[ptn.size()] = j;
	} // getnext(const string&, Vector<int>&)


	/* 利用KMP算法在主串str中的pos位置开始搜索模式ptn,
	 * 设next数组已知
	 * 若找到返回第一次出现的位置, 否则返回str.size()
	 */
	int KmpSearchKernel(const string& str, const string& ptn,
						int pos, const Vector<int>& next) {

		int i = pos, j = 0;
		while ( i < str.size() && ( j == -1 || j < ptn.size() ) ) {
			if ( j == -1 || str[i] == ptn[j] ) {
				++i; ++j;			// 继续比较后继字符
			} else {
				j = next[j];		// 模式串向右移动
			}
		}
		if ( j == ptn.size() )
			return i - ptn.size();

		return str.size();
	} // KmpSearchKernel(const string&, const string&, int, const Vector<int>&)


} // namespace

/* 利用KMP算法在主串str中从pos开始搜索模式ptn,
 * 若找到返回第一次出现的位置, 否则返回str.size()
 */
int KmpSearch(const string& str, const string& ptn, int pos) {
	Vector<int> next;
	getnext(ptn, next);
	return KmpSearchKernel(str, ptn, pos, next);
} // KmpSearch(const string&, const string&, int)

/* 利用KMP算法在主串str中搜索所有模式ptn, (允许重叠)
 * 返回找到的下标的数组
 */
Vector<int> KmpSearchAll(const string& str, const string& ptn) {
	Vector<int> result;
	Vector<int> next;
	getnext(ptn, next);

	/* next[ptn.size()] 记录了模式全部匹配后下一个位置"失配"时的偏移量
	 * 允许重叠情况下下一个位置的寻找，
	 * 相当于搜索一个更长模式，在ptn.size()处失配的情况
	 */
	for (int i = 0; i < str.size(); i+=next[ptn.size()]) {
		i = KmpSearchKernel(str, ptn, i, next);
		result.pushBack(i);
	}
	
	if ( result.back() >= str.size() ) {	// 可能会有多余元素
		result.removeBack();
	}

	return result;

} // KmpSearchAll(const string&, const string&)


/* 利用KMP算法在主串str中搜索所有模式ptn, (不允许重叠)
 * 返回找到的下标的数组
 */
Vector<int> KmpSearchAllNoOverlap(const string& str, const string& ptn) {
	Vector<int> result;
	Vector<int> next;
	getnext(ptn, next);

	for (int i = 0; i < str.size(); i+=ptn.size()) {	// 每次跳过已找到的模式即可
		i = KmpSearchKernel(str, ptn, i, next);
		result.pushBack(i);
	}
	
	if ( result.back() >= str.size() ) {	// 可能会有多余元素
		result.removeBack();
	}

	return result;

} // KmpSearchAllNoOverlap(const string&, const string&)