C语言：“最长公共子串” 高手帮忙编个

描述] 现在有一些由英文字符组成的大小写敏感的字符串，你的任务是找到一个最长的字符串[x]，使得对于已经给出的字符串中的任意一个y,[x]或[反序后的x]是y的子串。

[关于输入] 输入的第一行是一个整数t (1 <= t <= 10),t表示测试数据的数目。

对于每一组测试数据，第一行是一个整数n (1 <= n <= 100)，表示已经给出n个字符串。

接下来n行，每行给出一个长度在1和100之间的字符串。

[关于输出] 对于每一组测试数据，输出一行，给出题目中要求的字符串x的长度。

请帮忙///如何计算两个 字符串的最长公共子串

算法：求两个字符串的最长公共子串原理：（1） 将连个字符串分别以行列组成一个矩阵。

（2）。

若该矩阵的节点对应的字符相同，则该节点值为1。

(3)当前字符相同节点的值 = 左上角（d[i-1, j-1]）的值 +1，这样当前节点的值就是最大公用子串的长。

（s2） b c d e(s1)a 0 0 0 0b 1 0 0 0c 0 2 0 0d 0 0 3 03. 结果：只需以行号和最大值为条件即可截取最大子串C# code:[csharp] view plaincopyprint?public static string MyLCS(string s1, string s2) { if (String.IsNullOrEmpty(s1) || String.IsNullOrEmpty(s2)) { return null; } else if (s1 == s2) { return s1; } int length = 0; int end = 0; int[,] a = new int[s1.Length, s2.Length]; for (int i = 0; i = 0 && j - 1 >= 0) ? a[i - 1, j - 1] : 0; a[i, j] = s1[i] == s2[j] ? 1+n : 0; if (a[i, j] > length) { length = a[i,j]; end = i; } } } return s1.Substring(end - length + 1, length); }...

求最长公共子串 递归写的

展开全部 //刚写的！public class StringTest { public static void main(String[] args) { String s1 = ＂321abcDEFG123456＂; String s2 = ＂45DEFG123489＂; String str=method(s1,s2,0,s2.length(),3>2); System.out.println(＂\n＂+s1+＂\n\n＂+s2+＂\n\n最大公共子串=>＂+str); } private static String method(String s1, String s2,int t,int w,boolean b) { if(t>=w)return null; String str=s2.substring(t, w); if(s1.contains(str)) return str; else if(b) return method(s1,s2,++t,w,b=!b); else return method(s1,s2,t,--w,b=!b); }}...

考“软考”的软件设计师,该看什么书？

展开全部 要参加软件设计师的考试，务必购买两本书：《软件设计师教程》《教程》建议买教育部指定的教材，《软件设计师历年试题解析》。

《解析》倒也无所谓，张友生老师的分析似乎更全面、更有针对性。

另外还有《软件设计师大纲》，在复习过程中阶段性地查一查，梳理一下知识结构体系，可以查缺补漏。

1、具体学习每门课程的方法（1）软件工程。

软件工程是复习的重点，不但上午题当中占10左右，而且下午题里也有2道软件设计分析方面的题目，一定要熟练的掌握书本中说到的各种软件分析设计方法及有关的分析用图，对各种图的功能作用和制作方法（特别是各种图的组成元素）以及各种图之间的转换及联系（如果有的话），UML面向对象的软件设计方法及面象过程的软件设计方法完全理解，软件测试要达到理解的程度，其它的内容只有去强记了，因为基本是都是上午题，而且每年的题都不定，但与CMM有关的一定会有。

（2）数据库。

数据库部分也很重要，上午有5分左右，下午至少有一道数据库的题目，而且也一定是考关系型数据库，E-R模式也要搞懂，可由它导出关系，一定要弄懂关系数据库的几个范式及关系的建立方法。

因此，就要对关系数据库的基础概念非常清楚，如键的定义，函数依赖，范式的定义、作用及转换是建立关系的基础。

数据的并发控制，要熟练掌握SQL常用的几个语句，最好是用笔将每个语句写上几遍，对语句的各种形式加深记忆，数据库的学习还是不太难的。

因为考试不会考数据的物理存储及数据安全，感觉这方面的知识更难，交叉学科更多。

（3）学习数据结构和算法。

数据结构和算法是考试的重点内容，它的复习以普通的教材为主，对数组、链表、队列、栈、树及堆等基本的数据组织方式要非常熟悉（要做到看见算法就知道要用什么数据组织方式更高效），排序、索引及图的各种算法要了然于心（算法的分析过程及代码要非常清楚），算法的分析方法达到理解应用的水平。

对C语言要非常熟练（要会应用C语言语句的一些技巧，如可以利用函数的返回值做为判定条件，在循环中对数组的处理可使用a[i++]来提高编写代码的效率，这类的小技巧只有通过大量的阅读代码才能提高），如果是初学面向对象方面的高级语言，建议还是先学C++，感觉它更象一种语言规范，而Java是一种编程的工具并且由于它的跨平台特性所以它有很多自己独有的功能和特点，有时间一定要看一本C++语言的数据结构，它能使你更全面和深刻的理解类及对象的编程方法。

算法的学习不是一朝一夕就能提高的，一定要静下心来学习一些经典算法，比如：穷举法、贪婪法、分治法、迭代法、递推法、递归法、回溯法；找一些有名的算法程序来分析，比如：背包问题、组合问题、斐波那契数列、马踏棋盘问题、货朗担问题、八皇后问题、迷宫问题、汉诺塔问题、约琴夫环问题等。

有了这些算法思想在你的头脑中扎根后，当看到问题，就自然的想起用什么方法来求最优解了。

（4）程序设计语言。

程序设计语言包括C语言、编译原理和面向对象的程序设计语言（通常以C++为例）。

编译原理一定会考词法分析，它是后面编译过程的基础。

主要考的内容是NFA与DFA的转换、正规式与有穷自动机的转换等。

文法分析有一年考过下午题，这科对初学者比较难，比较抽象，理论性也比较强，反正我是学了4个来月才学通一点，这课复习没什么技巧，听听希赛的“编译原理视频教程”，学起来更快一些。

C语言要掌握好三种基本结构、数组、链表、结构体、共用体、参数传递、指针及指针数组、指针函数等等。

面向对象的程序设计语言要对基本概念及初步应用要了解，考得不深。

（5）面向对象方法学。

面向对象方法学不但是上午的考试重点，也是下午的考试重点。

上午平均有12分左右，而下午有30分，一道与UML图形有关的题目，一道面向对象程序设计的选做题。

所以要好好掌握这一块。

UML当中的类图、用例图、状态图、协作图要掌握好，考试中会常出现。

（老师多次强调这个要学习的知识点，我通过做题，认为老师抓的很准。

）（6）操作系统。

操作系统没什么说得了，把它的几个功能模块搞清楚及相关的算法搞清楚就好了，如处理器的管理、存储管理、设备管理、文件管理及系统安全，其中我认为比较难理解的是PV操作（在并发进程中它的应用非常灵活）和中断（反正这个对我比较难），一定要把相关内容所讲到的算法及分析过程搞懂。

当然还要注意进程死锁的问题，段页式存储的问题。

其它课程的复习就按考试大纲进行，把里面的概念搞清楚，因为它大部分都是上午题。

2、看书与练习相结合“看书时要有目的性，带着任务走，；看后做题进行巩固，所以看了书以后，要找一两个相关的题来做一做。

如何使用C语言求解最长公共子字符串问题及相关的算法

假定字符串采用堆分配方式，编写一个程序，求两个字符串S和T的一个最长公共子串本题的思路：本题要实现的算法扫描两个字符串。

其中index指出最长公共子串在s中的序号，length指出最长公共子串的长度堆分配存储表示如下：typedef struct{char *ch;int length;}Hstring;Status MaxComString(Hstring S,Hstring T,int &length){index=0;length=0;i=0；//令i作为扫描字符串S的指针while(ij=0；//令j作为扫描字符串T的指针while(jif(s.ch[i]==T.ch[j]){//找一个子串，其在字符串S中的序号为i，长度为length1length1=i;for(k=1;S.ch[i+k]==T.ch[j+k];k++)length1++;if(length1>length){//将较大长度值赋给index与lengthindex=i;length=length1;}j=j+length1；//继续扫描字符串T中第j=length1个字符之后的字符}else{j++;}}//whilei++;}//whileprintf（＂最长公共子串：＂）；for(i=0;ireturn OK;}...

转载请注明出处51数据库 » 软件设计师 最长公共子串