`
viMory
  • 浏览: 57865 次
  • 性别: Icon_minigender_1
  • 来自: 土卫六
最近访客 更多访客>>
社区版块
存档分类
最新评论

关于资料上子串距离的一种尝试性纠正

 
阅读更多

             资料上的子串距离定义如下:    

 设uv分别为长度是nm的字,p是它们的最大公共子串的长度,uv的子串距离定义为dS(u, v) = n+m−2p

            先来看海明距离,他是计算同一位置的不同元素的个数,很明显左图的海明距离为3.但对于子串距离,如按定义去解那就是 8+8-2*5=6,公共子串长度为5嘛,所以子串距离应为6.但实际上看图只有2啊,是不是资料错了?下午还专门去找老师请教了一翻,吐血的是老师说他早就知道这个错误了,但没拿出解决方案。我怀疑这个定义中的公式写错了,应该是dS(u,v)=max(n,m)-p。怎么得出来的,是看图看出来的。只要拿长度最大的串减去最大公共子串就是子串距离了,另外一张图也证实了我这一看法:图中的海明距离为32,但子串距离仅为6,我的计算是32-26=6,而不是32+32-2*26。

              

            跟老师说了,他觉得也是这样的,但没看到定义前不知道到底正确不?网上又找不到子串距离的相关介绍。原文是英语的,不向国内出售版权。难道还要逼我去看那个组合数学。抓狂中...

分享到:
评论

相关推荐

    编辑距离与最长公共子串(字符串的相似度)

    用本程序可得到字符串的相似度和字符串的公共子串以及编辑距离。

    删除子串删除子串删除子串删除子串,只要是原串中有相同的子串就删掉,不管有多少个

    KMP算法是一种在文本中查找模式(子串)的高效算法,它避免了不必要的字符比较,提高了搜索效率。 首先,我们需要理解KMP算法的基本原理。KMP算法通过构造部分匹配表来避免回溯,使得在搜索模式串时,当出现不匹配...

    把符串中的一子串替换为另一子串

    ### 把字符串中的一子串替换为另一子串——VB技术实现 在计算机编程领域,字符串操作是一项非常基础且重要的技能。特别是在Visual Basic (VB)这样的语言中,字符串处理经常被用于各种应用场合,比如文本处理、数据...

    判定一个串是否为另一个串的子串

    此程序为VC6.0实现判断一个字符串是否为另一个字符串的子串

    输出最长子串的代码

    在编程领域,"最长子串...总的来说,找到多个字符串的最长公共子串是一个典型的字符串处理问题,动态规划提供了一种高效且易于理解的解决方案。在实际应用中,这种技术可以用于文本相似性检测、基因序列分析等领域。

    双回文子串的相关解法

    ### 双回文子串的相关解法 #### 一、双回文子串与后缀...需要注意的是,虽然Manacher算法在这种类型的问题中有着更高的效率和简洁性,但对于学习和理解后缀数组等高级数据结构来说,上述方法不失为一种好的实践方式。

    在一个字符串中查找子串的个数

    根据给定的信息,本文将详细解释如何在一个字符串中查找特定子串出现的次数,并通过提供的代码示例来进一步阐述这一过程。我们将从以下几个方面进行深入探讨: ### 1. 字符串与子串的基本概念 #### 1.1 字符串 在...

    查找最长公共子串

    动态规划是一种利用已解决问题的解来构建更复杂问题的解的方法,它能有效地避免重复计算,提高效率。 动态规划解决方案通常涉及构建一个二维数组dp,其中dp[i][j]表示字符串a的前i个字符和字符串b的前j个字符的最长...

    从一个字符串中获取到指定位置指定大小的子串

    获取指定位置指定大小的子串是指从一个给定的字符串中,根据指定的起始位置和结束位置,获取一个子串。 在实现该功能时,我们需要使用到字符串处理函数,例如strlen、strcpy、memset等。这些函数提供了基本的字符串...

    VB 编写删除子串过程

    在VB(Visual Basic)编程中,删除子串是一项常见的字符串操作任务,主要用于处理文本数据,例如清理、格式化或修改用户输入。以下将详细介绍如何在VB中编写删除子串的过程,以及相关的知识点。 首先,我们需要了解...

    字符串的子串删除问题

    字符串的子串删除问题 在本文中,我们探讨了Codeforces Round #452 (Div. 2) F题的两种解决方案。该问题的关键点在于字符串的子串删除问题。 1. 问题描述 给定一个长度为n的字符串和m次操作,每次操作给出两个...

    找出子串位置.doc

    - 在 `getoccur` 方法中,我们使用了一个 `while` 循环,当 `indexOf` 返回值大于 -1 时,意味着找到了子串,此时更新计数器并移动索引以查找下一个子串。 - 在 `getoccur1` 方法中,我们使用了 `while (true)` ...

    最大连续子串问题

    在编程领域,"最大连续子串问题"是一个经典的数据结构和算法问题,主要涉及数组处理和动态规划。这个问题要求从给定的数组中找到一个连续子数组,使得这个子数组的元素之和最大。这个问题有多种解法,包括暴力枚举、...

    回文子串python实现

    给定一个字符串,计算这个字符串中有多少个回文子串。 ("回文串”是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就是回文串。)具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被...

    精彩编程与编程技巧-把符串中的一子串替换为另一子串...

    - **标题与描述**: “精彩编程与编程技巧-把字符串中的一子串替换为另一子串”。 - **核心内容**: 实现字符串中某个子串被另一个子串替换的功能。 #### 标签解析 - **标签**: “源代码” - **含义**: 提供了实现...

    在母串中查找某子串出现的最后位置

    在给定的标题“在母串中查找某子串出现的最后位置”中,我们要解决的问题是在一个主字符串(母串)中找到一个特定子字符串(子串)最后一次出现的索引位置。这个任务要求我们不依赖标准模板库(STL),这意味着我们...

    最短完备子串

    最短完备子串问题

    删除子串 vb

    在VB(Visual Basic)编程中,删除字符串中的子串是一项常见的操作,这通常涉及到字符串处理和文本操作。本文将深入探讨如何使用VB来实现这一功能,包括基础的字符串操作方法和一些实用技巧。 首先,VB提供了多种...

    求最长的公共子串

    两个字符串里求最长的公共子串

    子串的查找(非KMP)

    利用C++实现的一种简单的子串查找算法,仅使用循环判断进行了实现,若查找到子串则返回子串首字母在主串中的位置,如果不存在,则返回-1。有main()函数,可以直接运行使用。

Global site tag (gtag.js) - Google Analytics