Új hozzászólás Aktív témák

• #12437 opr nagyúr #83580928 #12429

  Új Válasz 2018-11-18 10:44:40 #12437

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  opr

  nagyúr

  válasz #83580928 #12429 üzenetére

  Van erre egy viszonylag egyszeru modszer is amugy:
  Mivel csak a leghoszabb ismetlodo kell, mas nem (hanyszor ismetlodik, hany darab ismetlodo van, stb), ezert eleg egyszeruen megirhato, ami ugy nez ki, hogy kezdesz a string hossza / 2-tol (compareLength), es ezt lepteted 1-esevel lefele, illetve compLength-hasonlitgatsz szeleteket, a stringen meg egyesevel lepkedsz elore (i). Egy masik ciklus meg annyit csinal, hogy (i) + compareLength-rol indul, es egyesevel compareLength meretu string szeleteket hasonlit ossze az elso ciklusbol kieso szelettel. Az elso adando alkalommal, amikor talal valamit, megvan a leghoszabb egyezes (mivel a leheto legnagyobb ismetlodo string az, ha a teljes hosszaban ketszer szerepel ugyanaz).

  Ez se tul optimalis, de nem olyan nehez megirni, es azert annyira nem veszesen lassu.

  Direkt nem irtam hozza kodot (meg pszeudot sem), mert igy meg kell erteni az implementalashoz a mindent.

• #12434 Domonkos addikt #83580928 #12429

  Új Válasz 2018-11-17 21:24:43 #12434

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Domonkos

  addikt

  válasz #83580928 #12429 üzenetére

  text=input().lower()
rep = []
for a in range(len(text)):
for b in range(a+1,len(text)):
ans = ''
i = 0
while (i < len(text) - b):
if text[a+i] == text[b+i] :
ans+= text[b+i]
i+=1
else:
break
rep.append(ans)
m = ''
for i in rep:
if len(i)>len(m):
m = i
if m == '':
print('None')
else:
print(m)

  Nem optimalis, de szerintem ertheto.

• #12432 kovisoft őstag #83580928 #12430

  Új Válasz 2018-11-17 15:37:40 #12432

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  kovisoft

  őstag

  válasz #83580928 #12430 üzenetére

  Egy lehetséges megoldás (bár nem optimális, mert közel n-köbös, de nem volt szempont a gyorsaság):

  Egy x változóval egyesével végigmész a karakterláncon. Minden egyes x pozícióra egy y változóval végigmész a rákövetkező karaktertől kezdve a fennmaradó pozíciókon. Egy h változóval addig mész, amíg az x és y kezdetű stringek karakterei megegyeznek, és amíg nincs átfedés (azaz x+h el nem éri az y-t). Tehát így h-ban lesz az aktuális ismétlődő szakasz hossza. Ha az így kapott h nagyobb, mint a korábban megjegyzett legnagyobb hossz, akkor megjegyzed a h hosszt és az x pozíciót egy-egy újabb változóban. Minden ciklus addig megy, amíg a string végére nem ér.

  Ha ennél gyorsabb algoritmus kellene, akkor keress rá a "prefix tree"-re, egy ilyen struktúra felépítésével lényegesen gyorsabban lehet ismétlődéseket keresni egy stringben.

• #12430 #83580928 törölt tag #83580928 #12429

  Új Válasz 2018-11-17 15:12:28 #12430

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  

  #83580928

  törölt tag

  válasz #83580928 #12429 üzenetére

  Az úgy például jó elgondolás, hogy mondjuk megnézem az első két karakterláncot (CG) és megnézem string maradék részében, hogy ismétlődik-e, ha igen akkor elmentem egy segédtömbbe. Utána megnézem az első három karaktert, megnézem hogy ismétlődik-e a maradék karakterekben, ha igen elmentem a segédtömb következő indexébe. Így tovább.Viszont ha az első két karakter nem ismétlődik, akkor tovább ugrok a következőre (GA).Ha mondjuk egy változóban mindig tárolnám a leghosszabb hosszt és ha mondjuk az elején lenne egy 4 karakternyi hosszúságú ismétlődés, akkor azután már 5 karakternyi hosszúságút keressen, mert a többi nem érdekel minket. Sokkal kevesebb találat lenne és kevesebb adat is kerülne a segédtömbbe. Ez így jó ? Meg eleve csak a string feléig kell keresnem, mert utána már nem ismétlődhet.

  Példa: CGACCGACCGAT

Új hozzászólás Aktív témák