你将收获

系列课程的目标是帮助学习者系统掌握数据结构课程的相关知识,具备利用这些知识分析问题、解决问题的能力。课程提供视频、课件、例程、自测、实践要求、参考解答等整套的解决方案,帮助学习者达到目标。本课是系列课程中的第4部分,具体目标包括:掌握用顺序表和链表实现栈存储的方法;掌握串在顺序存储结构下基本运算的实现;了解串在链式存储结构下基本运算的实现;掌握串的模式匹配算法。

适用人群

计算机相关专业学生

课程介绍

数据结构课程是计算机类专业的专业基础课程,在IT人才培养中,起着重要的作用。课程按照大学计算机类专业课程大纲的要求,安排教学内容,满足需要系统学习数据结构的人。系列课程包含11个部分,本课为第4部分串,介绍串的概念、用途,串的顺序和链式存储结构,以及在这两种结构下基本运算的实现,并介绍了模式匹配的经典算法。

课程讨论

老师 我觉得替换和删除的时候 应该要把i到j的节点的内存全部释放掉

所有回复(1):

技术方案并非唯一,你提出这样的想法就是对的。
贺老师为全国的信息学科学生做出了杰出的贡献!!!
老师讲的很到位,比直接看书学的快多了。

同学笔记

  • dkolli 2020-03-08 23:21:51

    来源:串的模式匹配(KMP算法) 查看详情

    终于学清楚KMP了

  • weixin_45416439 2020-02-13 12:55:50

    来源:串的模式匹配(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;
    }

    运行结果:

    欢迎留言评论~

没有更多了