學習筆記(01):資料結構基礎系列(4)：串-串的模式比對（KMP算法）

用KMP算法找出A中所有與B相同的子串的起始字元的下标

KMP算法的原理在BF算法的基礎上,通過計算B串的next[]數組的值,使得i一直增加不再回溯,j也不會直接回到0,而是回到next[j]的位置,是以降低了算法複雜度.一般的是找到第一個相同的子串就不再繼續找了,若我們繼續找下去,隻需要調整j的值就行了,找到一個比對的子串,就把下标存進容器當中,然後此時周遊A串的輔助變量i不變,将周遊B串的輔助變量j設定成next[j]即可,話不多說,上代碼!!

參考代碼:

#include<iostream>
#include<Windows.h>
#include<vector>
#define maxsize 256
using namespace std;
typedef struct sqstring {
	char data[maxsize];
	int len;
}qs;
void initstr(qs& s) {
	s.len = 0;
	s.data[0] = '\0';
}
void strAssign(qs& target, const char src[])
{
	if (sizeof(src) >= maxsize)
	{
		fprintf(stderr, "串長度不合适\n");
		return;
	}
	int i = 0;
	for (; src[i] != '\0'; i++)
	{
		target.data[i] = src[i];
	}
	target.data[i] = '\0';
	target.len = i;
}
void StrCpy(qs& target, qs& src)
{
	int i = 0;
	for (; src.data[i] != '\0'; i++)
	{
		target.data[i] = src.data[i];
	}
	//memcpy(target.data, src.data, sizeof(char) * src.len);//直接記憶體拷貝也可以
	target.data[src.len] = '\0';
	target.len = src.len;
}
bool StrEqual(qs& a, qs& b) {
	if (a.len != b.len) {
		return false;
	}
	else
	{
		int i = 0;
		for (; a.data[i]; i++)
		{
			if (a.data[i] != b.data[i]) {
				return false;
			}
		}
	}
	return true;
}
int GetLenght(qs& a) {
	return a.len;
}
//拼接
qs& Concat(qs& front, qs& back)
{
	qs ret;
	initstr(ret);
	if (front.len+back.len>=maxsize)
	{
		return ret;
	}
	int i = 0;
	for (; front.data[i]; i++)
	{
		ret.data[i] = front.data[i];
	}
	int j = i;
	for (; back.data[j - i]; j++)
	{
		ret.data[j] = back.data[j - i];
	}
	ret.data[j] = '\0';
	ret.len = front.len+back.len;
	return ret;
}
void PrinStr(qs& s) {
	printf("%s\n", s.data);
}
//求子串
qs& SubStr(qs&front,int i,int j) {
	qs m;
	initstr(m);
	if (i<=0||i>front.len||j<0||i+j-1>front.len )
	{
		return m;
	}
	int n = i-1,k=n;
	for (; k <n+j; k++)
	{
		m.data[k-n] = front.data[k];
	}
	m.data[j] = '\0';
	m.len = j;
	return m;
}
//插入 下标版
qs& Insert1(qs&target,qs&src,int i) 
{
	qs m;
	initstr(m);
	if (src.len+target.len>=maxsize||i>target.len+1)
	{
		return m;
	}
	int k = i - 1, j = 0;;
	for (; j <=k ; j++)
	{
		m.data[j] = target.data[j];
	}
	int l = j;
	for (;src.data[l - j]!='\0';l++)
	{
		m.data[l] = src.data[l - j];
	}
	int t = l;
	for (;target.data[k]!='\0';)
	{
		m.data[t++] = target.data[k++];
	}
	m.len = target.len + src.len;
	m.data[m.len] = '\0';
	return m;
}
//子串加拼接版
qs& Insert2(qs& target, qs& src, int i)
{
	qs m,p,q,s;
	initstr(m);
	initstr(p);
	initstr(q);
	initstr(s);
	if (src.len + target.len >= maxsize || i > target.len + 1)
	{
		return m;
	}
	int j = target.len - i ;
	p = SubStr(target, 1, i);
	q = Concat(p, src);
	s = SubStr(target, i+1, j);
	m = Concat(q, s);
	return m;
}
//删除
qs& DelStr(qs&s,int i,int j) {
	qs m;
	initstr(m);
	if (i<=0||i>s.len+1||j<0||i+j-1>s.len)
	{
		return m;
	}
	if (j==0)
	{
		return s;
	}
	int n = 0;
	for (; n < i-1; n++)
	{
		m.data[n] = s.data[n];
	}
	for (int k = i+j-1; s.data[k]; )
	{
		m.data[n++] = s.data[k++];
	}
	m.len = s.len - j;
	m.data[m.len] = '\0';
	return m;
}
//替換
qs& RepStr(qs&s,qs&m,int i,int j)
{
	qs q;
	initstr(q);
	if (i<=0||i>s.len||j<0||j>s.len||i+j-1>s.len)
	{
		return q;
	}
	int l = 0;
	for (; l < i-1; l++)
	{
		q.data[l] = s.data[l];
	}
	int k = l;
	for (; m.data[k-l];k++)
	{
		q.data[k] = m.data[k - l];
	}
	for (int t=i+j-1;s.data[t];)
	{
		q.data[k++] = s.data[t++];
	}
	q.len = s.len + m.len - j;
	q.data[q.len] = '\0';
	return q;
}
//比大小
int StrCompare(qs&s,qs&m){
	int min_len = 0;
	if (s.len>=m.len)
	{
		min_len = m.len;
	}
	else
	{
		min_len = s.len;
	}
	for (int i = 0; i < min_len; i++)
	{
		if (s.data[i]<m.data[i])
		{
			return -1;
		}
		else if(s.data[i]>m.data[i])
		{
			return 1;
		}
	}
	if (s.len>m.len)
	{
		return 1;
	}
	else if(s.len==m.len)
	{
		return 0;
	}
	return -1;
}
//求第一個最長的由相同的字元組成的子串
qs& LongsetSam(qs&s) 
{
	int lim[2] = { 0 };
	int max = 0,n=0;
	qs sam;
	initstr(sam);
	for (int i = 0; i < s.len;i++ )
	{
		if (s.data[i]==s.data[i+1])
		{
			n++;
		}
		else
		{
			if (n>max)
			{
				max = n;
				lim[0] = i - max + 1;
				lim[1] = i;
			}
			n = 1;
		}
	}
	for (int i = lim[0]; i<=lim[1]; i++)
	{
		sam.data[i - lim[0]] = s.data[i];
	}
	sam.len = max;
	sam.data[sam.len] = '\0';
	return sam;
}
//重載<<運算符
ostream& operator<<(ostream&os,vector<int>A) {
	if (!A.size())
	{
		os << "未找到比對的子串!" << endl;
		return os;
	}
	for (int i = 0; i < A.size(); i++)
	{
		os << "第:" << i + 1 << "個相同串的下标為:" << A[i] << endl;
	}
	return os;
}
//找打s中所有與t相同的子串的起始下标 BF字元串模式比對
void find_all_sam(qs&s,qs&t,vector<int>&a) {
	int i = 0, j = 0;
	while (i < s.len && j < t.len)
	{
		while (i < s.len && j < t.len)
		{
			if (s.data[i] == t.data[j])
			{
				i++, j++;
			}
			else
			{
				i = i - j + 1;
				j = 0;
			}
		}
		if (j >= t.len)
		{
			a.push_back(i - t.len);
			j = 0;
		}
		else
		{
			return;
		}
	}
}
//計算next[j]
void getnext(qs&s,int next[]) 
{
	int i = 0, k = -1;
	next[0] = -1;
	while (i<s.len-1)
	{
		if (k==-1||s.data[i]==s.data[k])
		{
			i++;
			k++;
			next[i] = k;
		}
		else
		{
			k = next[k];
		}
	}
}
//KMP算法
void KMP(qs& s, qs& t, int next[],vector<int>&a)
{
	getnext(t, next);
	a.clear();
	int i = 0, j = 0;
	while (i < s.len && j < t.len)
	{
		while (i < s.len && j < t.len)
		{
			if (j==-1||s.data[i] == t.data[j])
			{
				i++, j++;
			}
			else
			{
				j = next[j];
			}
		}
		if (j >= t.len)
		{
			a.push_back(i - t.len);
			j = next[j];
		}
		else
		{
			return;
		}
	}

}
int main(int argc,char*argv[]) {
	qs p,q,n;
	vector<int>a;
	int next[maxsize] = { 0 };
	initstr(p);
	strAssign(p, "abbcacbbabab");
	initstr(q);
	strAssign(q, "ab");
	initstr(n);
	strAssign(n, "aabbcacbbababweababbcacbbababrteabbcacbbababqwabbabbcacbbabab");
	cout << "與Q串相同的子串比對開始:" << endl;
	KMP(n, q, next, a);
	cout << a;
	cout << "與P串相同的子串比對開始:" << endl;
	KMP(n, p, next, a);
	cout << a;
	system("pause");
	return 0;
}
           

運作結果:

歡迎留言評論~