最系列
常见到最长子序列，最长公共子序列等，网上总结了也很多．但自己实现一次方才了解．发现收获很多的．
目录
最长公开子序列
这个最基础，动态规划；转移方程:
C[i,j] = 0; 初始
C[i,j] = C[i-1,j-1] + 1; Xi = Yi
C[i,j] = max(C[i-1,j], C[i,j-1]); Xi != Yi;
**代码
#include <stdio.h>
#include <string.h>
int LCS(char *str1, char *str2, int m, int n, int len[][100],int sub[][100])
{
int i,j;
for(i=0;i<m;i++)
len[i][0] = 0;
for(i=0;i<n;i++)
len[0][i] = 0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
if(str1[i-1]==str2[j-1])
{
len[i][j] = len[i-1][j-1] + 1;
sub[i][j] = 0;
}
else if(len[i-1][j]>=len[i][j-1])
{
len[i][j] = len[i-1][j];
sub[i][j] = 1;
}
else
{
len[i][j] = len[i][j-1];
sub[i][j] = -1;
}
}
return len[m][n];
}
void PrintSub(char *x,int i, int j, int b[][100])
{
if(i==0||j==0)
return;
if(b[i][j] == 0)
{
PrintSub(x,i-1,j-1,b);
printf("%c",x[i-1]);
}
else if(b[i][j]==1)
PrintSub(x,i-1,j,b);
else
PrintSub(x,i,j-1,b);
return ;
}
int main()
{
char str1[100],str2[100];
int len1,len2;
int subq[100][100],subq_len[100][100];
while(~scanf("%s %s",str1,str2))
{
len1 = strlen(str1);
len2 = strlen(str2);
int len = LCS(str1,str2,len1,len2,subq_len,subq);
printf("%d\n",len);
PrintSub(str1,len1,len2,subq);
printf("\n");
}
return 0;
}
最长公开子串
串和序列的区别在于连续与否，两者实现也差不多
**代码
#include <stdio.h>
#include <string.h>
int LCS(char *str1, char *str2, int m, int n, char *str3, int len[][100])
{
int i,j;
int max = -1;
int x,y;
int k;
for(i=0;i<m;i++)
len[i][0] = 0;
for(i=0;i<n;i++)
len[0][i] = 0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
if(str1[i-1]==str2[j-1])
len[i][j] = len[i-1][j-1] + 1;
else
len[i][j] = 0;
if(len[i][j]>max)
{
max = len[i][j];
x = i;
y = j;
}
}
k = max;
str3[k] = '\0';
while(k>=0)
str3[--k] = str1[--x];
return max;
}
int main()
{
char str1[100],str2[100];
char str3[100];
int len1,len2;
int subq_len[100][100];
while(~scanf("%s %s",str1,str2))
{
len1 = strlen(str1);
len2 = strlen(str2);
int len = LCS(str1,str2,len1,len2,str3,subq_len);
printf("%s\n",str3);
printf("%d\n",len);
}
return 0;
}
最大子数组和
即一个数组中连续元素和的最大值，如1,2,-4,2 最大是3
**代码:
#include <stdio.h>
#include <limits.h>
int main()
{
int n, a[100];
int i,sum,tmp;
int maxsum ;
while(~scanf("%d",&n))
{
maxsum = INT_MIN;
sum = tmp = 0;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
tmp += a[i];
if(tmp<0)
tmp = 0;
else
sum = tmp;
if(sum>maxsum)
maxsum = sum;
}
if(maxsum<=0)
{
maxsum = a[0];
for(i=0;i<n;i++)
if(a[i]>maxsum)
maxsum = a[i];
}
printf("%d\n",maxsum);
}
return 0;
}
最大子数组
序列可以为数组，也可以为特别的结构体，原理应该是一样的 **代码：
#include <stdio.h>
#include <string.h>
//return the length
int LongIncreaseSubsquence1(int *a, int n, int *b)
{
int i,j;
int lenght = 1;
if(n<=0)return 0;
if(n==1)return 1;
b[0] = 1;
for(i=1;i<n;i++)
{
b[i] = 1;
for(j=0;j<i;j++)
{
if(a[j]<a[i]&&b[j]+1>b[i])
b[i] = b[j] + 1;
}
}
for(i=1;i<n;i++)
lenght = (lenght>=b[i]?lenght:b[i]);
return lenght;
}
int main()
{
int a[100];
int b[100];
int n,i;
while(~scanf("%d",&n))
{
for(i=0;i<n;i++)
scanf("%d",&a[i]);
int len = LongIncreaseSubsquence1(a,n,b);
printf("%d\n",len);
}
return 0;
}
还有两种方法： – 1.基于最长公共子序列，先把原串排序，再求最长公共子序列 – 2.再查找b[n]的时候，用二分法，因为b[n]是递增的序列
最大各子矩阵
最长重复子串
最长回文子串
最大M子段
字符编码距离
两个字符串，从其中一个变为另外一个需要的操作次数就是编码距离，这个或者还有其它的名词称谓．
操作只有三种最基本的，即增删改，例如abc和bcd的距离就是，abc删除a，再后面添加d，操作就两步
这种有一个很简单的方法，基于最长公共子序列，首先求出最长公共子序列int len = GetLongestCommomSubsquence(str1,str2),然后得到两个字符串长度，len1,len2.则操作的距离是len1+len2-len*2
当这几个系列的操作都了解后，好多字符串的处理都是基于此的
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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | |
待续