Pseudokod - hledani podretezce – Funkcionální programování – Fórum – Programujte.com

Zdravim,

ve skole sme meli nasledujici ukol:

Zjisteti zda se v retezci A nachazi podretezec B.

A: abxy2cdef.

B: 2cd.

i <- 0
while a[i] != '.'
  j <- 0
     while b[j] =! '.'
	if b[j] != a[i+j]
          break
     j <- j+1
	if b[j] = '.'
	  return true
	return false

Takle sme to vyresili ve skole. Ale nemuzu pochopit jak si mam vysvetlit tu cast kde: a[i +j], proste nechapu jak se tam pracuje s tema indexama,mohl by mi to prosim nekdo osvetlit, popr. upravit?

Diky moc                    

Ahoj,

zřejmě se jedná o implementaci metody "prosté síly".

konkrétně v případě a[i + j] se jedná o to, že i je pozice "1. znaku porovnávaného textu"-značí se"src" a j pozici porovnávaného bodu v řetězci B - značí se "pattern".

jinak řečeno:

• i se posouvá od 0 do (délka_řetězce - 1) // v tvém konkrétním případě je konec řetězce značen tečkou
• a[0] se porovná s prvním znakem b neboli b[0], potom a[1] s b[1] atd.. No když není nalezená shoda, posune se i = 1, b = 0 a musí se posunout na a[1+0 = 1] a zase porovnat s b[0], a[1+1 = 2] vs b[1], a[1+2 = 3] vs b[2] ..
• další krok i = 2, b = 0 - >a [2+0 = 2] vs b[0], a[2+1 = 3] vs b[1], a[2+2 = 4] vs b[1]...
• A obecně z toho vidíš že musíš porovnávat a[i + j] a b[j]
• konec samozřejmě nastává když b[j] == '.' .. neboli byl uspěšně porovnán celý pattern řetězec => byl nalezen podřetězec, případně doběhnul hlavní cyklus a shoda nebyla nalezena.

Blbě se to vysvětluje, líp se to kreslí http://www.youtube.com/watch?…

BTW: Funkcionální programování je trošku něco jínýho, ale to je tedko vedlejší:) Bazinga

diky moc, tohle sem presne potreboval vedet i to video je supr ;)

Keď sa to volá Brute force aký iný spôsob hľadania ešte je?