※ [本文轉錄自 Test 看板 #1Ssj-ha- ]
作者: fun5566 (裱高中化學題目出錯之神) 看板: Test
標題: [測試] dsa hw4 test
時間: Tue May 14 23:32:57 2019
[HW4] 請問樓下 以下的Output file無誤吧? 若無誤,
請問Output file的x=? ,謝謝!
Output file
x 4533
Just a legend
Input file
3
StringAndSubstringDescriptionYouaregivenastringsandanintegerm,yourtaskistosolv
etwoproblems:Findalongeststringt,sothattisasubstringofs,andappearsatleastmtime
sins.Thedefinitionofsubstringisasequenceofconsecutivecharactersinastring.Forex
ample,s=baaaababababbababbab,m3,thentheanswerwouldbebabab,sincethereisnoothers
ubstringofsislongerthanbababandappearsatleast3timesinstrings.Findalongeststrin
gr,suchthatrisaprefixofsandasuffixofs.Inotherwords,risthebeginningofthestrings
andtheendofthestrings.Tomakeitmorechallenging,stringralsoneedtobeabletobelocat
edsomewhereinsidethestrings,thatis,itisneitherbeginning,noritsend.Forexample,s
=abcdabcabc,theanswerisabc,becauseitappearsatpositions0prefix,4neitherprefixno
rsuffix,7suffix,whichmeetstherequirements.InputFormatTheinputcontainsseveralte
stcases.Eachtestcaseconsistsofalinewithanintegermm1,theminimumnumberofrepetiti
ons,followdbyalinecontainingastrings.Allcharactersinsarelowercasecharactersfro
matoz.Thelasttestcaseisdenotedbym0andmustnotbeprocessed.OutputFormatForeachtes
tcase,youneedtoprinttwolinesofanswers:Forproblem1,ifthereisnosolution,outputno
newithoutthequotes;otherwise,printtwointegersinaline,separatedbyaspace.Thefirs
tintegerdenotesthemaximumlengthofasubstringappearingatleastmtimes;thesecondint
egeristherightmostpossiblestartingpositionofsuchasubstring.Forproblem2,printth
estringthatmeetstherequirements.Ifasuitablestringdoesnotexist,thenprintJustale
gendwithoutthequotes.IntroductionFolklore,legends,mythsandfairytaleshavefollow
edchildhoodthroughtheages,foreveryhealthyyoungsterhasawholesomeandinstinctivel
oveforstoriesfantastic,marvelousandmanifestlyunreal.ThewingedfairiesofGrimmand
Andersenhavebroughtmorehappinesstochildishheartsthanallotherhumancreations.Yet
theoldtimefairytale,havingservedforgenerations,maynowbeclassedas"historical"in
thechildren'slibrary;forthetimehascomeforaseriesofnewer"wondertales"inwhichthe
stereotypedgenie,dwarfandfairyareeliminated,togetherwithallthehorribleandblood
curdlingincidentsdevisedbytheirauthorstopointafearsomemoraltoeachtale.Moderned
ucationincludesmorality;thereforethemodernchildseeksonlyentertainmentinitswond
ertalesandgladlydispenseswithalldisagreeableincident.Havingthisthoughtinmind,t
hestoryof"TheWonderfulWizardofOz"waswrittensolelytopleasechildrenoftoday.Itasp
irestobeingamodernizedfairytale,inwhichthewondermentandjoyareretainedandthehea
rtachesandnightmaresareleftout.L.FrankBaumChicago,April,1900.1.TheCycloneDorot
hylivedinthemidstofthegreatKansasprairies,withUncleHenry,whowasafarmer,andAunt
Em,whowasthefarmer'swife.Theirhousewassmall,forthelumbertobuildithadtobecarrie
dbywagonmanymiles.Therewerefourwalls,afloorandaroof,whichmadeoneroom;andthisro
omcontainedarustylookingcookstove,acupboardforthedishes,atable,threeorfourchai
rs,andthebeds.UncleHenryandAuntEmhadabigbedinonecorner,andDorothyalittlebedina
nothercorner.Therewasnogarretatall,andnocellarexceptasmallholedugintheground,c
alledacyclonecellar,wherethefamilycouldgoincaseoneofthosegreatwhirlwindsarose,
mightyenoughtocrushanybuildinginitspath.Itwasreachedbyatrapdoorinthemiddleofth
efloor,fromwhichaladderleddownintothesmall,darkhole.WhenDorothystoodinthedoorw
ayandlookedaround,shecouldseenothingbutthegreatgrayprairieoneveryside.Notatree
norahousebrokethebroadsweepofflatcountrythatreachedtotheedgeoftheskyinalldirec
tions.Thesunhadbakedtheplowedlandintoagraymass,withlittlecracksrunningthroughi
t.Eventhegrasswasnotgreen,forthesunhadburnedthetopsofthelongbladesuntiltheywer
ethesamegraycolortobeseeneverywhere.Oncethehousehadbeenpainted,butthesunbliste
redthepaintandtherainswasheditaway,andnowthehousewasasdullandgrayaseverythinge
lse.WhenAuntEmcametheretoliveshewasayoung,prettywife.Thesunandwindhadchangedhe
r,too.Theyhadtakenthesparklefromhereyesandleftthemasobergray;theyhadtakenthere
dfromhercheeksandlips,andtheyweregrayalso.Shewasthinandgaunt,andneversmilednow
.WhenDorothy,whowasanorphan,firstcametoher,AuntEmhadbeensostartledbythechild's
laughterthatshewouldscreamandpressherhanduponherheartwheneverDorothy'smerryvoi
cereachedherears;andshestilllookedatthelittlegirlwithwonderthatshecouldfindany
thingtolaughat.UncleHenryneverlaughed.Heworkedhardfrommorningtillnightanddidno
tknowwhatjoywas.Hewasgrayalso,fromhislongbeardtohisroughboots,andhelookedstern
andsolemn,andrarelyspoke.ItwasTotothatmadeDorothylaugh,andsavedherfromgrowinga
sgrayasherothersurroundings.Totowasnotgray;hewasalittleblackdog,withlongsilkyh
airandsmallblackeyesthattwinkledmerrilyoneithersideofhisfunny,weenose.Totoplay
edalldaylong,andDorothyplayedwithhim,andlovedhimdearly.Today,however,theyweren
otplaying.UncleHenrysatuponthedoorstepandlookedanxiouslyatthesky,whichwaseveng
rayerthanusual.DorothystoodinthedoorwithTotoinherarms,andlookedattheskytoo.Aun
tEmwaswashingthedishes.Fromthefarnorththeyheardalowwailofthewind,andUncleHenry
andDorothycouldseewherethelonggrassbowedinwavesbeforethecomingstorm.Therenowca
measharpwhistlingintheairfromthesouth,andastheyturnedtheireyesthatwaytheysawri
pplesinthegrasscomingfromthatdirectionalso.SuddenlyUncleHenrystoodup."There'sa
cyclonecoming,Em,"hecalledtohiswife."I'llgolookafterthestock."Thenherantowardt
heshedswherethecowsandhorseswerekept.AuntEmdroppedherworkandcametothedoor.Oneg
lancetoldherofthedangercloseathand."Quick,Dorothy!"shescreamed."Runforthecella
r!"TotojumpedoutofDorothy'sarmsandhidunderthebed,andthegirlstartedtogethim.Aun
tEm,badlyfrightened,threwopenthetrapdoorinthefloorandclimbeddowntheladderintot
hesmall,darkhole.DorothycaughtTotoatlastandstartedtofollowheraunt.Whenshewasha
lfwayacrosstheroomtherecameagreatshriekfromthewind,andthehouseshooksohardthats
helostherfootingandsatdownsuddenlyuponthefloor.Thenastrangethinghappened.Theho
usewhirledaroundtwoorthreetimesandroseslowlythroughtheair.Dorothyfeltasifshewe
regoingupinaballoon.Thenorthandsouthwindsmetwherethehousestood,andmadeittheexa
ctcenterofthecyclone.Inthemiddleofacyclonetheairisgenerallystill,butthegreatpr
essureofthewindoneverysideofthehouseraisedituphigherandhigher,untilitwasatthev
erytopofthecyclone;andthereitremainedandwascarriedmilesandmilesawayaseasilyasy
oucouldcarryafeather.Itwasverydark,andthewindhowledhorriblyaroundher,butDoroth
yfoundshewasridingquiteeasily.Afterthefirstfewwhirlsaround,andoneothertimewhen
thehousetippedbadly,shefeltasifshewerebeingrockedgently,likeababyinacradle.Tot
odidnotlikeit.Heranabouttheroom,nowhere,nowthere,barkingloudly;butDorothysatqu
itestillonthefloorandwaitedtoseewhatwouldhappen.OnceTotogottooneartheopentrapd
oor,andfellin;andatfirstthelittlegirlthoughtshehadlosthim.Butsoonshesawoneofhi
searsstickingupthroughthehole,forthestrongpressureoftheairwaskeepinghimupsotha
thecouldnotfall.Shecrepttothehole,caughtTotobytheear,anddraggedhimintotherooma
gain,afterwardclosingthetrapdoorsothatnomoreaccidentscouldhappen.Hourafterhour
passedaway,andslowlyDorothygotoverherfright;butshefeltquitelonely,andthewindsh
riekedsoloudlyallaboutherthatshenearlybecamedeaf.Atfirstshehadwonderedifshewou
ldbedashedtopieceswhenthehousefellagain;butasthehourspassedandnothingterribleh
appened,shestoppedworryingandresolvedtowaitcalmlyandseewhatthefuturewouldbring
.Atlastshecrawledovertheswayingfloortoherbed,andlaydownuponit;andTotofolloweda
ndlaydownbesideher.Inspiteoftheswayingofthehouseandthewailingofthewind,Dorothy
soonclosedhereyesandfellfastasleep.