求两个字符串的最大公共子串
把字符串1(长度m)横排，串2(长度n)竖排，得到一个m×n的矩阵c，矩阵的每个元素的值如下，如果m[i]=n[j]，则c[j][i]=1,否则，c[j][i]=0。然后找出矩阵中连续是1的对角线最长的一个，则对角线的长度就是公共子串的长度.
经过改进，可以不需要构造矩阵，因为第i行如果有字母匹配，其取值仅与第i-1行相关，若m[i]=n[j]，则c[j][i] = c[j-1][i-1] + 1，这样仅需要记录一个长度为m的一维数组就可以了。
鼓捣出来的代码如下：
#include
#include
char * StringSearch( char * str1, char * str2 )
{
int i;
int j;
char* ptempBuffer1;
char* ptempBuffer2;
char* pwork;
char* plast;
char* ptemp;
char* retstr;
int resultIndex = 0;
int resultLength = 0;
int str1Size = 0;
int str2Size = 0;
ptempBuffer1 = str1;
while( *ptempBuffer1 != ' ' )
{
ptempBuffer1++;
str1Size++;
}
ptempBuffer2 = str2;
while( *ptempBuffer2 != ' ' )
{
ptempBuffer2++;
str2Size++;
}
ptempBuffer1 = ( char * ) malloc( str1Size );
pwork = ptempBuffer1;
memset( pwork, 0, str1Size );
ptempBuffer2 = ( char * ) malloc( str1Size );
plast = ptempBuffer2;
memset( plast, 0, str1Size );
for( i = 0; i < str2Size; i++ )
{
for( j = 0; j < str1Size; j++ )
{
if( *( str1 + j ) == *( str2 + i ) )
{
if( j == 0 )
{
*( pwork + j ) = 1;
}
else
{
*( pwork + j ) = *( plast + j - 1 ) + 1;
}
if( resultLength < *( pwork + j ) )
{
resultIndex = j;
resultLength = *( pwork + j );
}
}
else
{
*( pwork + j ) = 0;
}
}
ptemp = pwork;
pwork = plast;
plast = ptemp;
}
retstr = ( char * ) malloc( resultLength + 1 );
memcpy( retstr, str1 + resultIndex - resultLength + 1, resultLength );
*( retstr + resultLength ) = ' ';
printf( "resultIndex = %d, resultLength = %dn", resultIndex, resultLength );
free( ptempBuffer1 );
free( ptempBuffer2 );
return retstr;
}
int main(int argc, char *argv[])
{
char* ret = NULL;
ret = StringSearch( "adbccadebbca", "edabccadece" );
printf( "result String is %sn", ret );
free( ret );
system("PAUSE");
return 0;
}
为了方便，采用了两个容量为m的一维数组来保存运行中的结果，空间复杂度为m+n+2*m(保存打印输出的结果字符串可以不需要)，也就是O(m+n)。由于需要事先遍历字符串得到长度，算法复杂度为m*n + m + n，O(m*n)级别。
---------------------------------------------------------
问题描述
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X=
例如，序列Z=
给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。例如，若X=和Y=
最长公共子序列(LCS)问题：给定两个序列X=
最长公共子序列问题LCS
问题描述
参考解答
动态规划算法可有效地解此问题。下面我们按照动态规划算法设计的各个步骤来设计一个解此问题的有效算法。
1.最长公共子序列的结构
解最长公共子序列问题时最容易想到的算法是穷举搜索法，即对X的每一个子序列，检查它是否也是Y的子序列，从而确定它是否为X和Y的公共子序列，并且在检 查过程中选出最长的公共子序列。X的所有子序列都检查过后即可求出X和Y的最长公共子序列。X的一个子序列相应于下标序列{1, 2, …, m}的一个子序列，因此，X共有2m个不同子序列，从而穷举搜索法需要指数时间。
事实上，最长公共子序列问题也有最优子结构性质，因为我们有如下定理：
定理: LCS的最优子结构性质
设序列X=
若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列;
若xm≠yn且zk≠xm ，则Z是Xm-1和Y的最长公共子序列;
若xm≠yn且zk≠yn ，则Z是X和Yn-1的最长公共子序列。
其中Xm-1=
证明
用反证法。若zk≠xm，则
由于zk≠xm，Z是Xm-1和Y的一个公共子序列。若Xm-1和Y有一个长度大于k的公共子序列W，则W也是X和Y的一个长度大于k的公共子序列。这与Z是X和Y的一个最长公共子序列矛盾。由此即知Z是Xm-1和Y的一个最长公共子序列。
与 2.类似。
这个定理告诉我们，两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。
2.子问题的递归结构
由最长公共子序列问题的最优子结构性质可知，要找出X=
由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如，在计算X和Y的最长公共子序列时，可能要计算出X和Yn-1及Xm-1和Y的最长公共子序列。而这两个子问题都包含一个公共子问题，即计算Xm-1和Yn-1的最长公共子序列。
与矩阵连乘积最优计算次序问题类似，我们来建立子问题的最优值的递归关系。用c[i,j]记录序列Xi和Yj的最长公共子序列的长度。其中Xi=< x1, x2, …, xi>，Yj=
3.计算最优值
直接利用(2.2)式容易写出一个计算c[i,j]的递归算法，但其计算时间是随输入长度指数增长的。由于在所考虑的子问题空间中，总共只有θ(m*n)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。
计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=
Procedure LCS_LENGTH(X,Y);begin m:=length[X]; n:=length[Y]; for i:=1 to m do c[i,j]:=0; for j:=1 to n do c[0,j]:=0; for i:=1 to m do for j:=1 to n do if x[i]=y[j] then begin c[i,j]:=c[i-1,j-1]+1; b[i,j]:="↖"; end else if c[i-1,j]≥c[i,j-1] then begin c[i,j]:=c[i-1,j]; b[i,j]:="↑"; end else begin c[i,j]:=c[i,j-1]; b[i,j]:="←" end; return(c,b);end;
由于每个数组单元的计算耗费Ο(1)时间，算法LCS_LENGTH耗时Ο(mn)。
4.构造最长公共子序列
由算法LCS_LENGTH计算得到的数组b可用于快速构造序列X=
下面的算法LCS(b,X,i,j)实现根据b的内容打印出Xi与Yj的最长公共子序列。通过算法的调用LCS(b,X,length[X],length[Y])，便可打印出序列X和Y的最长公共子序列。
Procedure LCS(b,X,i,j);begin if i=0 or j=0 then return; if b[i,j]="↖" then begin LCS(b,X,i-1,j-1); print(x[i]); {打印x[i]} end else if b[i,j]="↑" then LCS(b,X,i-1,j)
else LCS(b,X,i,j-1);end;
在算法LCS中，每一次的递归调用使i或j减1，因此算法的计算时间为O(m+n)。
例如，设所给的两个序列为X=和Y=
j 0 1 2 3 4 5 6
i yj B D C A B A
┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐
0 xi │ 0 0 0 0 0 0 │
│ ↑ ↑ ↑ ↖ ↖ │
1 A │ 0 0 0 0 1 ← 1 1 │
│ ↖ ↑ ↖ │
2 B │ 0 1 ← 1 ← 1 1 2 ← 2 │
│ ↑ ↑ ↖ ↑ ↑ │
3 C │ 0 1 1 2 ← 2 2 2 │
│ ↖ ↑ ↑ ↑ ↖ │
4 B │ 0 1 1 2 2 3 ← 3 │
│ ↑ ↖ ↑ ↑ ↑ ↑ │
5 D │ 0 1 2 2 2 3 3 │
│ ↑ ↑ ↑ ↖ ↑ ↖ │
6 A │ 0 1 2 2 3 3 4 │
│ ↖ ↑ ↑ ↑ ↖ ↑ │
7 B │ 0 1 2 2 3 4 5 │
└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘
图2 算法LCS的计算结果
5.算法的改进
对于一个具体问题，按照一般的算法设计策略设计出的算法，往往在算法的时间和空间需求上还可以改进。这种改进，通常是利用具体问题的一些特殊性。
例如，在算法LCS_LENGTH和LCS中，可进一步将数组b省去。事实上，数组元素c[i,j]的值仅由c[i-1,j-1]，c[i-1,j]和 c[i,j-1]三个值之一确定，而数组元素b[i,j]也只是用来指示c[i,j]究竟由哪个值确定。因此，在算法LCS中，我们可以不借助于数组b而 借助于数组c本身临时判断c[i,j]的值是由c[i-1,j-1]，c[i-1,j]和c[i,j-1]中哪一个数值元素所确定，代价是Ο(1)时间。 既然b对于算法LCS不是必要的，那么算法LCS_LENGTH便不必保存它。这一来，可节省θ(mn)的空间，而LCS_LENGTH和LCS所需要的 时间分别仍然是Ο(mn)和Ο(m+n)。不过，由于数组c仍需要Ο(mn)的空间，因此这里所作的改进，只是在空间复杂性的常数因子上的改进。
另外，如果只需要计算最长公共子序列的长度，则算法的空间需求还可大大减少。事实上，在计算c[i,j]时，只用到数组c的第i行和第i-1行。因此，只要用2行的数组空间就可以计算出最长公共子序列的长度。更进一步的分析还可将空间需求减至min(m, n)
以字符数组a作为循环，分别求以a第一个字符、第二个字符，。。。，第strlen(a)个字符打头的最长公共串。从而求出最长公共字串。
写完程序后发现有问题，要是有两个以上且不相等的最长公共串，就出现问题了，不过用二维数组去储存也许不会出现问题，但是问题就变得复杂了。或许真得像楼主一样，先计算出最长公共串的长度再求公共串。
C/C++ code
#include
#include
#include
int longest_length_of_comstr(char *str1, char *str2);
int find_the_longest_comstr(char *str1, char *str2);
int find_the_longest_comstr(char *str1, char *str2)
{
int maxlen=longest_length_of_comstr(str1,str2);
int len;
int num=strlen(str1) > strlen(str2) ? strlen(str1)+1 : strlen(str2)+1;
char *p,*q,*tmp1,*tmp2,*maxi;
char *comstr=(char *)malloc(sizeof(char)*num);
for (q=str1; *q!=0; q++)
for (p=str2; *p!=0; p++)
{
len=0;
tmp1=q;
tmp2=p;
while (*tmp1 && *tmp2 && *tmp1==*tmp2)
{
tmp1++;
tmp2++;
len++;
}
if(len == maxlen)
{
maxlen=len;
maxi=q;
strncpy(comstr,maxi,maxlen);
*(comstr+maxlen)=0;
printf("%sn",comstr);
break;
}
}
free(comstr);
return 0;
}
int longest_length_of_comstr(char *str1, char *str2)
{
int maxlen=0;
int len;
char *p,*q,*tmp1,*tmp2;
for (q=str1; *q!=0; q++)
for (p=str2; *p!=0; p++)
{
len=0;
tmp1=q;
tmp2=p;
while (*tmp1 && *tmp2 && *tmp1==*tmp2)
{
tmp1++;
tmp2++;
len++;
}
if(len > maxlen)
{
maxlen=len;
}
}
return maxlen;
}
int main(void)
{
char a[]="abcaadybc";
char b[]="kbcdadwbc";
find_the_longest_comstr(a,b);
return 0;
}
C/C++ code
int main(void)
{
char a[]="abcaadybc";
char b[]="kbcdadwbc";
// find_the_longest_comstr(a,b);
//先假设b的长度小于a的长度
int i,j,maxLength;
int aLen = strlen(a) ;
int bLen = strlen(b) ;
char *comstr,*tempstr ;
comstr = (char * )malloc(sizeof(char)*bLen) ;
tempstr = (char * )malloc(sizeof(char)*bLen) ;
maxLength = 0 ;
j = 0 ;
for(i=0; i< aLen;i++)
{
int templen = 0 ;
int tempi = 0;
int point = 1 ;
while((tempi < aLen) && (j < bLen))
{
while(a[tempi] == b[j])
{
tempstr[templen++] = b[j] ;
tempi++ ;
j++ ;
}
if(templen > maxLength)
{
maxLength = templen ;
strcpy(comstr,tempstr) ;
}
tempi = i ;
point++ ;
templen = 0 ;
j = point ;
}
j = 0 ;
}
printf("%sn",comstr) ;
get) ;
return 0;
}
2.编写函数实现字符串分割。SourceStr为源串，splitStr为分割字符串，SplitStr中的每一个字符在SourceStr被看作是分
割符。函数需要返回被分割符分割好的字符串链表。 例如： 如果
SourceStr为“this is pen ,that is a ball.”。 SplitStr 为“, .”
则返回的字符串链表每一项值分别为：“this” “is” “ pen”…
struct Node
{
int value;
Node* next;
};
void creat_list(Node*& head)
{
int num=0;
while (1)
{
cin>>num;
if (num==-1)
{
break;
}
Node* p=new Node;
p->value=num;
p->next=head->next;
head->next=p;
}
}
void print_all(Node* head)
{
Node* q=head->next;
while(q)
{
cout<
q=q->next;
}
cout<<endl;< p="">
}
void list_sort(Node* head)
{
Node* p=head,*q=NULL;
while(1)
{
p=head;
for(;p->next!=q;p=p->next)
{
if (p->value>p->next->value)
{
int temp=p->value;
p->value=p->next->value;
p->next->value=temp;
}
}
q=p;
if (head->next==q)
{
break;
}
}
}
void two_list_sort(Node* head,Node* head1,Node*& new_list)
{
list_sort(head);
list_sort(head1);
print_all(head);
print_all(head1);
Node* p=head->next;
Node* p1=head1->next;
while (p&&p1)
{
if (p->value<=p1->value)
{
Node* m=new Node;
m->value=p->value;
m->next=new_list->next;
new_list->next=m;
p=p->next;
}
else
{
Node* m=new Node;
m->value=p1->value;
m->next=new_list->next;
new_list->next=m;
p1=p1->next;
}
}
while (p)
{
Node* m=new Node;
m->value=p->value;
m->next=new_list->next;
new_list->next=m;
p=p->next;
}
while (p1)
{
Node* m=new Node;
m->value=p1->value;
m->next=new_list->next;
new_list->next=m;
p1=p1->next;
}
list_sort(new_list);
}
int main()
{
Node* head=new Node;
Node* head1=new Node;
head->next=NULL;
head->value=0;
head1->next=NULL;
head1->value=1;
creat_list(head);
creat_list(head1);
print_all(head);
print_all(head1);
Node* new_list=new Node;
new_list->next=NULL;
new_list->value=0;
two_list_sort(head,head1,new_list);
print_all(new_list);
return 0;
}3.编写函数，检查给定字符串是否整数，如果是，返回其整数值
long __cdecl atol(
const char *nptr
)
{
int c; /* current char */
long total; /* current total */
int sign; /* if '-', then negative, otherwise positive */
/* skip whitespace */
while ( isspace((int)(unsigned char)*nptr) )
++nptr;
c = (int)(unsigned char)*nptr++; sign = c; /* save sign indication */
if (c == '-' || c == '+')
c = (int)(unsigned char)*nptr++; /* skip sign */
total = 0;
while (isdigit(c)) //isdigit如果为0-9之间的数返回真 否则为假
{
total = 10 * total + (c - '0'); /* accumulate digit */
c = (int)(unsigned char)*nptr++; /* get next char */
}
if (sign == '-')
return -total;
else
return total; /* return result, negated if necessary */
} 。
#include
bool findInt(char a[],int len,int &num);
void main()
{
char a[5]={'-','5','4','2','1'};
int num;
if(findInt(a,5,num))
cout<<num;< p="">
else
cout<<"转换失败!";
}
bool findInt(char a[],int len,int &num)
{
num=0;
bool flag;
if(a[0]=='+')
flag=0;
else if(a[0]=='-')
flag=1;
else
return false;
for(int x=1;x<len;x++)< p="">
{
if(a[x]>='0'&&a[x]<='9')
{
num=num*10+(a[x]-'0');
}
else
{
return false;
}
}
if(flag)
num=0-num;
return true;