`
standalone
  • 浏览: 613081 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

最长公共子串问题解答

    博客分类:
  • c++
阅读更多

编写一个程序,对输入的字符串s和t,求其最长的公共子字符串。

【输入形式】 从屏幕分行读入串s和t。s和t由任意字符构成,长度都不超50个字符。输入数据确保只有唯一的最长公共子串。如果没有公共子串,打印No Answer

【输出形式】 在单独行上输出串s和串t的最长公共子串,在结尾输出一个回车符。

//作者:baihacker
//时间:9.12.2006
 
#include <stdio.h> 
#include <string.h>

int b[50][50];
int c[50][50];

void lcs(x,m,y,n)
char *x;
int  m;
char *y;
int  n;
{
 int i;
 int j;

 for (i=1;i<=m;i++) c[i][0] = 0;
 for (i=1;i<=n;i++) c[0][i] = 0;
 c[0][0] = 0;
 for (i=1;i<=m;i++)
  for (j=1;j<=n;j++)
  {
   if (x[i-1] == y[j-1])
   {
    c[i][j] = c[i-1][j-1] + 1;
    b[i][j] = 1;
   }
   else
    if (c[i-1][j] > c[i][j-1])
    {
     c[i][j] = c[i-1][j];
     b[i][j] = 2;
    }
    else
    {
     c[i][j] = c[i][j-1];
     b[i][j] = 3;
    }

  }
}

void show(i,j,x)
int i;
int j;
char* x;
{
 if (i==0||j==0)
  return;
 if (b[i][j]==1)
 {
  show(i-1,j-1,x);
  printf("%c",x[i-1]);
 }
 else
  if (b[i][j]==2)
   show(i-1,j,x);
  else
   show(i,j-1,x);
}

void main() 
{ 
  char* x="aabcdababce";
  char* y="12abcabcdace";
  int m = strlen(x);
  int n = strlen(y);
  lcs(x,m,y,n);
  show(m,n,x);

} 
 
分享到:
评论

相关推荐

    一些C语言中字符串的算法问题解决实例小结

    问题1:找两个字符串的最长公共子串。  具体描述,如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串。注意,并不要求子串(字符串一)的字符必须连续出现在...

    javascript-leetcode面试题解动态规划问题之第1143题最长公共子序列-题解.zip

    最长公共子序列不考虑子序列在原字符串中的相对位置,而最长公共子串则要求子序列必须连续。 对于这个问题,我们可以构建一个二维数组dp,其中dp[i][j]表示字符串s1的前i个字符与字符串s2的前j个字符的最长公共子...

    2015年上半年 程序员 应用技术1

    - **动态规划**:最长公共子串问题可以使用动态规划解决,通过比较字符串中不同长度的子串,记录最长公共子串的信息。 3. **编程语言理解** - **C 语言**:试题二和试题三涉及到 C 语言编程,要求填充代码以实现...

    计算机常见算法面试题.docx

    `commanstring`函数寻找两个字符串`shortstring`和`longstring`的最长公共子串。它首先尝试直接在`longstring`中查找`shortstring`,如果找不到则使用KMP算法逐个字符地比较,找出最长的公共子串。 以上是这些面试...

    算法分析与设计第3章课后习题答案.doc

    本篇文章将详细介绍和分析课后习题中涉及的三个重要问题:矩阵链乘积、最长公共子串以及0/1背包问题,同时展示动态规划在解决这些问题中的应用。 首先,让我们聚焦于矩阵链乘积问题。当我们面临多个矩阵进行连续...

    动态规划的经典题目 包括分析和解答

    例如,在最长公共子序列问题中,我们可以根据两个子串的最长公共子序列长度来更新原序列的长度。 3. **边界条件**:设定初始状态或基础情况,通常是问题规模最小的情况,可以直接求解。例如,当背包容量为0或者物品...

    lintcode算法分析和解答

    - **最长公共子串(Longest Common Substring)** - 寻找两个字符串之间的最长公共子串。 - **旋转字符串(Rotate String)** - 实现字符串的循环左移或右移操作。 - **反转字符串中的单词(Reverse Words in a String)...

    leetcode java解答答案

    - 字符串处理也很常见,比如检查回文、最长公共前缀等。Java的String类提供了丰富的API来处理字符串。 2. **链表**: - 链表题目通常涉及节点的插入、删除和遍历。Java中的LinkedList类提供了链表操作的基础,但...

    C笔试题总结

    具体实现取决于题目要求,例如最长公共子串、最长回文子串等。 6. **字符串转换为整数**: - C语言标准库提供了`strtol`函数来实现字符串到整数的转换。也可以手动实现,从字符串的开头开始,逐个字符转换,注意...

    大学算法课程设计相关算法C,Java版解答

    4. **动态规划**:动态规划是一种解决最优化问题的常用方法,如背包问题、最长公共子序列、斐波那契数列等。它的核心思想是将大问题分解为小问题,并存储中间结果以避免重复计算。 5. **递归与回溯**:递归是编程中...

    LCS.rar_LCS

    最长公共子序列是指两个字符串中,不考虑顺序的最长的子串,这个子串同时存在于两个原始字符串中。例如,对于字符串"ABCDGH"和"ACDFGHR",它们的一个最长公共子序列是"ACDFG"。注意,LCS并不考虑子序列中的字符顺序...

    POJ1836-Alignment

    在对齐问题中,可能需要找出两个字符串之间的最长公共子序列或最长公共子串,这是字符串处理中的经典问题。 4. **贪心算法**:另一种可能的解决方案是贪心策略,通过每次做出局部最优选择,期望得到全局最优解。...

    LeetCode 算法

    4. **字符串(String)**:字符串处理题目涵盖正则表达式匹配、模式查找、最长公共子串等。常用方法有KMP算法、动态规划等。 5. **二叉树(Binary Tree)**:二叉树题目包括构建、遍历、平衡化、查找、修改等。常见...

    算法艺术与信息学竞赛习题答案

    其次,书中可能涉及动态规划,这是解决复杂问题的有效方法,如背包问题、最长公共子序列、矩阵链乘等。动态规划的核心思想是将大问题分解为小问题,并通过状态转移方程求解。 此外,字符串处理也是信息学竞赛中常见...

    浙江大学ACM题解代码

    4. **动态规划**:动态规划是一种解决最优化问题的高效方法,如背包问题、最长公共子序列、矩阵链乘法等。 5. **贪心算法**:在每一步选择局部最优解,最终达到全局最优,如霍夫曼编码、活动安排问题等。 6. **...

    ACM 北大POJ二百多道题目解答

    1. **基础算法**:排序(快速排序、归并排序、冒泡排序等)、搜索(二分查找、深度优先搜索、广度优先搜索等)、动态规划(背包问题、最长公共子序列等)、贪心算法(活动选择、最小生成树等)。 2. **数据结构**:...

    HackBulgaria-Algorithms:进入HackBulgarias课程算法问题的解决方案

    5. **动态规划**:这是一种优化问题求解的方法,适用于解决具有重叠子问题和最优子结构的问题,如背包问题、最长公共子序列等。 6. **贪心算法**:适用于在每一步选择局部最优解,从而得到全局最优解的问题,例如...

    算法期末代码+简答123123

    9. **字符串处理**:可能涉及模式匹配,如KMP算法,或者字符串操作,如最长公共前缀、最长重复子串等。 10. **计算几何**:可能包含点、线、面之间的关系处理,如最近点对问题、凸包问题等。 在“算法代码+简答”...

    java算法 面试练习

    1. 动态规划是解决复杂问题的有效方法,例如背包问题、最长公共子序列、斐波那契数列等。 2. 理解状态转移方程和记忆化搜索,减少重复计算,提高效率。 四、递归与回溯 1. 递归:在解决递归问题时,需要理解递归的...

    计算机算法设计与分析答案

    动态规划解决最优化问题,如背包问题和最长公共子序列;贪心算法每次选择局部最优解以达到全局最优,如Prim算法构造最小生成树;回溯法用于搜索所有可能的解,如八皇后问题。 2. **数据结构基础**:算法往往基于...

Global site tag (gtag.js) - Google Analytics