Hány substring-je van egy string-nek?
A kérdés vonatkozik arra, hogy úgy mennyi van ahol az egyezőeket beleszámítjuk annyiszor ahányszor előfordul. Úgy is hogy hány különböző van.
Tudjuk ha a kérdés arra vonatkozik hogy hány különbőző van, az string függő, ha egyezőket beleszámítjuk akkor csupán a hossz függvénye.
A kérdés arra vonatkozik hogy lehet gyorsabban kiszámolni annál, hogy legeneráljuk az összes substring-jét.
Példák az összes substring legenerálással : [link]
"1. asdasd [0..6] 6"
Az "1." jelenti azt hogy hanyadik sorszámú a substring legenerálás közben. Utána következik az adott substring azaz "asdasd" (önmagának is substring-je egy string) , utána következik az index tartomány hogy mettől meddig tart az adott substing az eredetiben ez esetben ez [0..6] ez után következik az adott substing hossza ami itt 6 .
A példák melyekre végig van számítva brute force-al : asdasd , aaa, abaa, abcde, xxxxxx .
Nem tudom javítani ott.
Javítás : [link]
Még megjegyzés hogy az indextartomány alulról zárt fentről nyitott, azaz [0..6]-ban a 0.-ik indexű az alja, a teteje az 5.-ik indexű.
"ha n=string hosszúsága akkor (n(n-1))/2"
Egyszerűség kedvéért vegyük azt az esetet ahol minden substing különböző az indextartományok függvényében.
Tönkrevágja a gyk a formázást ezért nem közvetlen ide írom a példákat.
n=3
(n*(n-1))/2 = 3
"abc" esetében : [link]
Nem stimmel.
n=4
(n*(n-1))/2 = 6
"abcd" esetében : [link]
Nem stimmel.
n=1 esetében (n*(n-1))/2 = 0, triviális hogy a jó válasz az 1 lenne.
Rájöttem hogy (n+1)*n/2 esetében stimmel.
Már csak a nehezebb része van hátra a kérdésemnek.
válasza:Az egyedi substringek számát meg lehet állapítani lineáris időben: [link]
Ha ki is akarod írni őket, akkor az nyilván inputfüggő lesz O(n^2) worst case komplexitással, hiszen nem tudod megúszni annál kevesebb lépésből, mint ahány egyedi substring van benne, ami akár n(n+1)/2 is lehet.
Kapcsolódó kérdések:
Minden jog fenntartva © 2025, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!