子字符串查找(KMP算法 非DFA实现) -- C++实现


实现代码

// KMP.h
#ifndef KMP_H
#define KMP_H

#include "Component.h"

namespace jay{
	class KMP
	{
	public:
		KMP(string strTxt)
		{
			m_txt = strTxt;
			m_Next = nullptr;

		}
		~KMP()
		{
			if (m_Next != nullptr)
			{
				delete []m_Next;
				m_Next = nullptr;
			}
		}

		// 该算法的说明,请参考 详解KMP算法 .pdf 
		// 上机调试会比较容易明白
		void Next()
		{
			m_Next = new int[m_pat.length()];
			for (int i=0;i<m_pat.length();i++)
			{
				m_Next[i] = 0; 
			}

			m_Next[0] = -1;
			int j = 0;
			int k = -1;

			while (j < m_pat.length() - 1) 
			{
				if (k == -1 || m_pat.at(j) == m_pat.at(k)) 
				{
					if (m_pat.at(++j) == m_pat.at(++k)) 
					{ // 当两个字符相等时要跳过

						m_Next[j] = m_Next[k];

					} 
					else 
					{
						m_Next[j] = k;
					}
				} 
				else 
				{
					k = m_Next[k];

				}

			}
		}

		int Find(string strPat,int iBegin = 0)
		{
			if (strPat.length() == 0)
			{
				return -1;
			}

			// 初始化next数组
			m_pat = strPat;
			Next();

			// 主串的位置
			int i = iBegin;
			// 模式串的位置
			int j = 0; 

			int iTxtLength = m_txt.length();
			int iPatLength = m_pat.length();
			while (i < iTxtLength && j < iPatLength) 
			{

				if (j == -1 || m_txt.at(i) == m_pat.at(j)) 
				{ 
					// 当j为-1时,要移动的是i,当然j也要归0
					i++;
					j++;

				} 
				else 
				{
					// i不需要回溯了
					// i = i - j + 1;
					j = m_Next[j]; // j回到指定位置
				}
			}

			if (j == m_pat.length()) 
			{

				return i - j;
			} 
			else 
			{
				// 查找失败
				return -1;

			}
		}
	private:
		string m_txt;
		string m_pat;
		int *m_Next;
	};
};

#endif

测试代码

//main.cpp
#include "Component.h"
#include "KMP.h"
using namespace jay;

int main(int argc, char* argv[])
{
    // 书本的DFA版本理解起来有点费劲,回头有时间再处理
	string txt = "qwhafhsjhfq87121378yqsdhfq927121278042yr5123qw8r098qthghasdfjhghajf08791212q9483r09q3uif12369a";
	string pat = "1212";
	KMP kmp(txt);
 	int index1 = kmp.Find(pat);
 	cout << index1 << endl;
	cout << kmp.Find(pat,index1+3) << endl;
	cout << kmp.Find("69a",index1+3) << endl;
}

 

暂无评论

注册用户登录后才能发表或者回复评论,请先登录 注册。