資源描述：
《Pattern Matching with Wildcards based on Key Character Location》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
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
