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

• #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.

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