3、串、KMP、矩阵_答案

1、一个nn的对称矩阵，如果以相同的元素只存储一次的原则进行压缩存储，则其元素压缩后所需的存储容量为 n(n+1)/2 。2、一个串的任意连续字符组成的子序列称为串的 子串 ，该串称为 主串 。3、串长度为0的串称为 空串 ，只包含空格的串称为 空格串 。4、若两个串的长度相等且对应位置上的字符也相等，则称两个串 相等 。5、寻找子串在主串中的位置，称为 模式匹配 。其中，子串又称为 模式串 。6、求出二维数组An,n的两条对角线元素之和（程序题）。int sumOfDiagonal(int *a)int i, n = a0.length, sum1 = 0, sum2 = 0, sum;for (i = 0; i 0and xi=yjmaxCi-1,j,Ci,j-1 if i,j0and xiyj2 、给定一个源串和目标串，能够对串进行如下操作：（2012.Baidu、google）在给定位置上插入一个字符串。替换任意字符删除任意字符使得源串等于目标串，源串和目标串的长度都小于2000。 求出相似度=（操作次数+1）/2。注：距离=操作次数解：对第一个字符进行操作：删除A或B前增加一个字符，将变成A2,lenA和B1,lenB。 对第一个字符进行操作：删除B或A前增加一个字符，将变成A1,lenA和B2,lenB。 对第一个字符进行操作：修改A或修改B的字符，将变成A2,lenA和B2,lenB。 设fi,j表示strAi,lenA与strBj,lenB的最小距离，则：fi,jfi+1,j+1 strAi=strBj minfi+1,j+1,fi,j+1+1,fi+1,j+1+1 其他 3、 求数组的子数组之和的最大值。一个有N个整数元素的一维数组( A0, A1, . , An-2, An-1)，子数组之和的最大值是什么?(要求子数组的元素是连续的)例子：有数组( -2, 5, 3, -6, 4, -8, 6)，则其子数组之和的最大值为8，其对应的数组为(5,3)Allk+1=maxAk+1，Ak+1+Startk，Allk.#define INTMIN 0x80000000int getMaxSum(int a,int len)int max=INTMIN;int sum=0;int i=0;for(i=0;ilen;i+)if(aimax)max=sum;return max;4、 递归（全排列）templatevoid Swap(Type &a,Type &b)Type t;t=a;a=b;b=t;templatevoid Perm_Cpp(Type list,int k,int m)/产生listk:m的所有全排列if(k=m) /只剩一个元素for(int i=0;i=m;i+)coutlisti;coutendl;else/还有多个元素待排列，递归产生排列for(int i=k;ich);S-len = strlen(S-ch)/sizeof(char);i = 0;while(S-chi != 0 & i len)k = 0;while(S-chi = S-chi+k)k+;if(*max chi != 0 & i len)k = 0;while(S-chi = S-chi+k)k+;if(*max = k) ccount = S-chi;Locationcount = i;count+;i = i + k;ccount = 0;/输出字符平台及对应的初始位置void PrintString(int *max, char cN, int LocationN)int i, k;printf(最大字符平台为：n);for(i = 0; ci != 0; i+) for(k = 0; k *max; k+)putchar(ci);printf(n对应初始位置为：%3dn,Locationi+1);void main()SString S;int max;int LocationN;char cN; MaxStr(&S, &max, c, Location);PrintString(&max, c, Location);6、 鞍点是指矩阵中的元素aij是第i行中值最小的元素，同时又是第j列中值最大的元素。试设计一个算法求矩阵A的所有鞍点。#includeint main() int n, m, i, j, k, l, minn, maxx, flag ; int a256256; while(1) printf(请输入矩阵的行列数：n); scanf(%d %d,&n,&m); printf(请输入与行列数相符的矩阵：n); for(i=0; in; i+) for(j=0; jm; j+) scanf(%d,&aij); flag=0; printf(马鞍点输出(输出该点所在的行数与列数)：n); for(i=0; in; i+) for( j = 0; j m; j+) minn = aij; for( k = 0 ; k aik) break; if( k=m) maxx=aij; for(l=0; ln; l+) if(maxxalj) break; if(l=n) printf(%d %d %dn,i , j ,aij); flag = 1; if(flag=0) printf(此矩阵没有马鞍点n); return 0;7、 字符串反序void reverse(char *str) if(*str=0) return; int len=strlen(str); char c=*str; *str=strlen-1; strlen-1=0; reverse(str+1); strlen-1=c;void reverse2(string &str) int