子序列和子串问题算法的全面总结_子串和子序列

1.分清楚什么是子串，什么是子序列

看文章前首先要搞清楚什么是子序列，什么是子串；子序列是指一个字串中非连续的字串，例如：字串A：123456789 它有一个子序列a：13579（非连续） 它有一个子串b：12345（连续）。

2.有关子串问题的算法

（1）最大子串

何为最大子串，例如：最大子串是要找出由数组成的一维数组中和最大的连续子串。比如{5,-3,4,2}的最大子串就是 {5,-3,4,2}，它的和是8,达到最大；而 {5,-6,4,2}的最大子串是{4,2}，它的和是6。

求解最大子串的代码如下所示：
（使用c语言）

int maxSubSum(const vector<int> &arr,int &begin,int &end)  //arr是数组
{
	int maxSum=0;//输出最大子串的和
	int currSum=0;
	int newbegin=0;
	for(int i=0;i<arr.size();i++)
	{
		currSum+=arr[i];
		if(currSum>maxSum)
		{
			maxSum=currSum;
			begin=newbegin;
			end=i;
		}
		if(currSum<0)
		{
			currSum=0;
			newbegin=i+1;
		}
	}
	return maxSum;
}
//找最大子序列的方法很简单，只要前i项的和还没有小于0那么子序列就一直向后扩展，否则丢
//弃之前的子序列开始新的子序列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

（2）最长公共子串

什么是最长公共子串？
最长公共子串是指两个字串，例如字串A：123456789
字串B：122466456 它们的最长公共子串就是456。注意：子串一定是连续的。

暴力求解最长公共子串（使用c语言）：

int longestSubstring(string x,string y)
{
	int xlen=x.size();
	int ylen=y.size();
	if(xlen==0||ylen==0)
	{
		return 0;
	}
	int max=-1;
	for(int i=0;i<xlen;i++)
	{
		for(int j=0;j<ylen;j++)
		{
			int m=i;
			int n=j;
			int len=0;
			while(m<xlen && n<ylen)
			{
				if(x[m]!=y[n])
				{
					break;
				}
				m++;
				n++;
				len++;
			}
			if(len>max)
			{
				max=len;
			}
		}
	}
	return max;
}
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

暴力方法很好理解，但是做题时往往不作为第一选择，待讲完子序列的方法后我会给你们讲解利用动态规划解决子串问题的算法，现在我再给你们讲一种特殊的算法，如下所示：

利用类似于直尺的比对方法求解最长公共子串

算法的基本思想就如图片所示，代码就看基本功如何，基本功好的很快就可以写出来了！！

代码的实现如下所示（c语言）：

int longestSubstring(string x,string y)
{
	int i,len1,len2,len,s1_start,s2_start,idx,curmax,max;
	len1=strlen(x);
	len2=strlen(y);
	len=len1+len2;
	max=0;
	for(i=0;i<len;i++)
	{
		s1_start=s2_start=0;
		if(i<len1)
		s1_start=len1-1;
		else
		s2_start=i-len1;
		//这段if和else目的是为了将两个字符串尺子进行移动，不断对齐到新的地方
		curmax=0;
		for(idx=0;(s1_start+idx<len1)&&(s2_start+idx<len2);idx++)//这个循环的作用是进行比对，判断它的最长公共子串
		{
			if(x[s1_start+idx]==y[s2_start+idx])
			curmax++;
			else
			{
				max=curmax>max?curmax:max;
				curmax=0;
			}
		}
		max=curmax>max?curmax:max;
	}
	return max;
	}
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

有关子序列问题的算法

（1）最长递增子序列

最长递增子序列问题的描述：设L=<a1,a2,…,an>是n个不同的实数的序列，L的递增子序列是这样一个子序列Lin=<aK1,ak2,…,akm>，其中k1<k2<…<km且aK1<ak2<…<akm。求最大的m值。

利用递推方法解决最长递增子序列问题

首先让们想一下，有一个字串A：1 2 3 4 5 6 7 8 9，我们将它放在一个数组B里面，从B[0]开始放，
有一个数组f[9]用来记录字串从1到9的每个数的递增数；比如说：f[4]里面放的就是到5的最长递增数，f[4]的值就是5；现在我们想想这个数是怎么得到的，是不是依次将f[0]到f[3]的大小比较一遍，选出其中一个最大的数+1赋值给f[4]；同时别忘了要满足B[4]>B[3]。现在让我们来实现我所说的这段话的代码。

递推法解决最长递增子序列问题代码如下所示:

int lis(float[] B)
{
	int n=B.length;
	int f[n];
	f[0]=1;
	for(int i=1;i<n;i++)
	{
		f[i]=1;
		for(int j=0;j<i;j++)
		{
			if(B[j]<B[i] && f[j]>f[i]-1)//这里的作用就是我上面说的比大小以及要满足递增
			f[i]=f[j]+1;
		}
	}
	return f[n-1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

利用动态规划方法解决最长递增子序列的问题

dp[ i ]以序列中第i个元素结尾的最长上升子序列的长度

那么状态转移方程为：if (a[i] > a[j]) dp[i] = MAX (dp[i], dp[j] + 1);

等等，是不是感觉这里有点熟悉，没错这个动态转移方程的思想就是原模原样照搬的递推算法的思想，话不多说，这里我就附上完整的代码（从网上找的）：

#include<cstdio>
 2 #include<cmath>
 3 #include<cstring>
 4 const int qq=1005;
 5 int dp[qq];
 6 int num[qq]; 
 7 int main()
 8 {
 9     int n;
10     while(~scanf("%d",&n)){
11         memset(dp,0,sizeof(dp));        // 5 6 7 8 1
12         for(int i=0;i<n;++i)
13         scanf("%d",&num[i]);
14         dp[0]=1;
15         int x=0;
16         for(int j,i=0;i<n;++i){
17             int maxn=0;
18             for(j=0;j<i;++j)    //这里利用了递推的原理、 
19                 if(num[i]>num[j])    //由前面的最长递增子序列推出后面的最长递增子序列、 
20                     maxn=maxn>dp[j]?maxn:dp[j];
21             dp[i]=maxn+1;
22             if(dp[i]>x)    x=dp[i];    //x记录的是当前的最大值、 
23         }
24         printf("%d\n",x);
25     }
26     return 0;
27 }
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

（2）最长公共子序列（相当经典的一个问题）

最长公共子序列的意思应该很明显了，我这就不多做解释，现在关键是代码的实现，我决定使用动态规划来解决这个问题！！！

利用动态规划解决最长公共子序列问题

当我们搜索这个问题的时候有两个图可以说很常见，我就拿着两幅图片来说事，我会给你们完全讲明白这两幅图中的含义！

这是动态规划的式子，引进一个二维数组c[][]，用c[i][j]记录X[i]与Y[j] 的LCS 的长度，b[i][j]记录c[i][j]是通过哪一个子问题的值求得的，以决定搜索的方向。

怎么用上面的动态规划式子来理解下面这幅图呢，首先上面这幅图就告诉了我们代码应该如何实现，第一步就应该将c[][]数组所有c[0][i]和c[i][0]的值初始化为0（这是为了方便求得最终LCS的数值），然后开始按照动态规划式子进行遍历，我们注意到图中有些格子右下角写的0，有些写的1等等，这些就是c[i][j]的值，图中涂黑的方块就是字串1：BDCABA和字串2：ABCBAB求得 最长公共子序列的整体过程。我们发现如果有两个字母相等，他就会往斜下方移动一格。

下面我上代码，你应该一下就可以明白了，如下所示：

int longestSubstring(string x,string y)
{
	int **c=new int*[x.size()+1];  //定义二维数组c
	for(int i=0;i<x.size();i++)
	{
		c[i]=new int [y.size()+1];
	}
	for(int i=0;i<=x.size();i++)c[i][0]=0;
	for(int i=0;i<=y.size();i++)c[0][i]=0;
	for(int i=1;i<=x.size();i++)//开始遍历整个c[][]数组！！
	{
		for(int j=1;j<=y.size();j++)
		{
			if(x[i]==y[j])
			{
				c[i][j]=c[i-1][j-1]+1;//这个地方其实就是图中的斜着移动，意思就是字串Xi和Yj相等c[i-1][j-1]存储的长度+1
			}
			else if(x[i]!=y[j])
			{
				c[i][j]=c[i-1][j]>c[i][j-1]?c[i-1][j]:c[i][j-1];//如果不等就是c[i-1][j]和c[i][j-1]中最大的一个，就是图中的竖着或者横
				//着移动
			}
		}
	}
	return c[x.size()][y.size()];
}
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

注意：还记得我上面所说的最长公共子串的动态规划解法么，现在已经可以很好地理解了其实就是在x[i-1]!=y[j-1]的时候，将c[i][j]=0，因为他是子串，并不连续。代码如下所示：

for(i = 0; i < len1+1; i++)
	c[i][0]=0;    //第0列都初始化为0
for(j = 0; j < len2+1; j++)
	c[0][j]=0;    //第0行都初始化为0 
max = -1;
int longestSubstring(string x,string y)
{
	int c[][];
	int max=-1;
	for(int i=1,i<=x.size();i++)
	{
		for(int j=1;j<=y.size();j++)
		{
			if(x[i-1]!=y[j-1]) c[i][j]=0;//只有这里不一样
			else if(x[i-1]==y[j-1]) c[i][j]==c[i-1][j-1]+1;
			if(max<c[i][j])
			{
				max=c[i][j];//这里也需要判别最长子串...
			}
		}
	}
	return max;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23