资源描述：
《Pattern Matching with Wildcards based on Key Character Location》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、PatternMatchingwithWildcardsbasedonKeyCharacterLocationa,cb,aaaaYinglingLiu,XindongWu,XuegangHu,JunGao,GongqingWu,aaHaipingWangandXiaoliHongaSchoolofComputerScienceandInformationEngineering,HefeiUniversityofTechnology,Hefei230009,ChinabDepartmentofComputerScience,Univer
2、sityofVermont,Burlington,VT05405,USAcSchoolofPhysics,UniversityofScienceandTechnologyofChina,Hefei230026,Chinaliuyingling22@gmail.comAbstractKalai[5]andMuthukrishanetal.[6]improvedthetimecomplexity.Coleetal.[7]changedtheproblemslightlyPatternmatchingwithwildcardsisacompl
3、exbyspecifyingthetotalnumberofwildcardsasaconstant.problemandthisproblemhaswidepotentialapplicationTheylimitedthetotallengthofthes,butthisisnotintextsearch,biologicalsequencesandinformationconvenienttotheuser.Manberetal.[8]improveditbysecurityetc.Weproposeanewalgorithmc
4、alleddefiningthenumberofsachangeablerange.InourQuicksearch,forpatternmatchingwithwildcardsandresearch,weconsiderachallengingproblemthatthelengthconstraintsbasedonkeycharacterlocationandrangeofthenumberofsbetweeneverytwoconsecutivesubspacepartition.Thisnewalgorithmincre
5、asesbylettersinthepatterncanbespecifiedseparately.This40%-60%searchingefficiencyincomparisonwithSAILconsiderationgivesmoreflexibilitiestotheuserforwhencharactersofpatternPintextTareunevenlyspecifyingquerypatternsthanotherresearchefforts.Indistributed..addition,wenotethat
6、arangeofsisjustalocalconstraintforaquerypatternandtheusermayalsowantKeywords:Algorithms,Patterns,Wildcards,Efficiencytospecifyarangeforthetotallengthofeachmatchingsubstringinwhichthepatternoccurs.Sowealsotakegloballengthconstraintsintoconsideration.RecentlyChenetal.[9]i
7、ntroducedanewalgorithm1.IntroductionSAILwhichsolvesthepatternmatchingwithwildcardsandlengthconstraints.InSAIL,ithasanonlinesearchingPatternmatchingisaclassicalproblem.Therehaveperiod,abackwardphaseandanoptimalmethod.Butbeenalotofresearcheffortsinthisarea.Patternwhenweana
8、lyzeSAILindepth,wefindSAILwouldmatchingwithwildcardsiscrucialinexploringvaluablerepeatsearchinginsomepl
