当前位置：文档之家 › On The Longest Common Subsequence Problem- General And Variants

On The Longest Common Subsequence Problem- General And Variants

  • 格式：pdf
  • 大小：299.85 KB
  • 文档页数：50

下载文档原格式

  / 50

合集下载

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

OnTheLongestCommonSubsequenceProblem-

GeneralAndVariants

AThesisSubmitted

inPartialFulfillmentoftheRequirements

fortheDegreeof

MasterofTechnology

by

SudheerKumarVootla

tothe

DEPARTMENTOFCOMPUTERSCIENCE&

ENGINEERING

INDIANINSTITUTEOFTECHNOLOGY,KANPUR

July2006Abstract

LetXandYbeanytwosequencesoveranalphabetΣ,whereeachpair

ofelementsinΣiscomparable.Thelongestcommonincreasingsubse-

quence(LCIS)problemistofindanincreasingsubsequenceScommonto

bothXandYofgreatestlength.

ForanytwosequencesXandYoveranalphabetΣ,thelongestcommon

subsequenceproblemofXandYistofindasubsequenceScommonto

bothXandYwithgreatestlength.UnliketheLCISproblemwhereevery

pairofinputalphabetiscomparable,thereisnosuchrestrictionintheLCS

problem.FurtherthegreatestcommonsubsequencefoundintheLCISmust

bestrictlyincreasing,whichneednotbethecaseforLCS.

LetX,YandPbeanythreesequencesoveranalphabetΣ.Thecon-

strainedlongestcommonsubsequence(CLCS)problemofXandYwithre-

specttoPistofindalongestcommonsubsequenceSofXandY,such

thatPisasubsequenceofS.

InthisthesisweproposeanalgorithmforsolvingtheLCISproblem.

OuralgorithmtakesO((n󰀏+m)loglogm)timeandO(n󰀏+mσ)space.

Here󰀏isthelengthoftheLCISandσisthesizeofthealphabet.

Wealsodescribeanalgorithmforretrievingthelongestcommonsub-

sequence(LCS).OuralgorithmtakesO(m󰀏logn+d)timeandO(n+|Σ|)

space.

Finally,weproposeanalgorithmfortheCLCSproblem.Ouralgorithm

takesO(r(m󰀏logn+d))timeandO(n+α+|Σ|)spacetoretrievetheCLCS.

iAcknowledgment

MyforemostthanksgotoDr.SanjeevSaxenaforhisinvaluablesupervision,

guidanceandsupport.Heconstantlyencouragedmeandgavemanyuseful

ideasthroughoutmyThesiswork.Thankyousir,yourguidanceisofgreat

helptomeforcompletingmyThesissuccessfully.Iwouldalsoliketothank

Sitaram,KiranandSivaKumarfortheirhelpduringmanyrestlessnights.

IwouldalsoliketotakethisopportunitytothankLakshman,Swamialong

withmyotherlabmatesRaviKumar,Sunil,Chandan,Abhijit,Sudeepaand

Anjaliforusefuldiscussionsandvaluablesuggestions.Imustalsothankour

DepartmentofComputerScienceandIITKanpurforprovidingmeworld-

classinfrastructurewithallthefacilitiesandstimulatingenvironment.

Myspecialthankstomyparentswhoshoweredimmenseloveonmeand

brothersfortheiraffectionandcontinuoussupportwithoutwhichthiswork

wouldnothavebeenpossible.

SudheerKumarVootla

July2006

IndianInstituteofTechnologyKanpur

iiContents

1Introduction1

1.1Preliminaries...........................1

1.2Organizationoftherestofthereport..............2

2Previouswork3

2.1TheLCISproblem........................3

2.2TheLCSproblem.........................4

2.3TheCLCSproblem........................5

3TheLCISProblem6

3.1Preliminaries...........................6

3.2AnalgorithmtofindtheLCIS[4]................8

3.2.1Algorithm.........................9

3.2.2Analysisofthealgorithm................9

3.3Ourapproach...........................10

3.4DataStructure..........................12

3.5Algorithm.............................14

3.5.1Preprocessing.......................14

3.5.2FindingLCIS.......................15

3.6Analysisofthealgorithm....................17

3.6.1TimeComplexity.....................17

3.6.2SpaceComplexity....................19

4TheLCSProblem20

4.1Introduction............................20

iii4.2Hirschberg’sMethod.......................21

4.3Sebastian’sMethod........................22

4.3.1Algorithm.........................23

4.3.2Complexity........................24

4.4Ourapproach...........................25

4.4.1Overview.........................25

4.4.2DetailedDescription...................25

4.4.3Algorithm.........................26

4.5Preprocessing...........................28

4.6Complexity............................28

4.6.1TimeComplexity.....................28

4.6.2Spacecomplexity.....................29

4.7Proofofcorrectness.......................30

5TheCLCSProblem31

5.1Introduction............................31

5.2Chin’swork............................31

5.3HeandArslan’swork......................35

5.4Ourapproach...........................37

5.5Algorithm.............................39

5.6Complexity............................40

5.6.1Timecomplexity.....................40

5.6.2Spacecomplexity.....................40

6Conclusions41

ivListofTables

2.1TheLCISproblem.........................3

2.2TofindthelengthoftheLCS...................5

2.3ToretrievetheLCS........................5

2.4TheCLCSproblem........................5

v