Akkor fussunk neki még1x, na nem mintha sikerülne, csak úgy:
Bocsánat.
Tegyük fel, hogy a szó n hosszúságú és 4 különböző betű van benne. (Ez nyilván nem jelent lényegi megszorítást, viszont így egyszerű az algoritmus.)
Legyen ord fv. bijektív megfeleltetés a szó betűi és a {0,1,2,3} halmaz között.
Legyen a szó a v tömbben tárolva.

  last[] <- {0,0,0,0}

  

  result <- 0

  for i = n-1 downto 0 do

  begin

    s <- result

 

    if last[ ord(v[i]) ] = 0 then

      result <- 2 * result + 1

    else

      result <- 2 * result - last[ ord(v[i]) ]

 

    last[ ord(v[i]) ] <- s

 

  end; 	

Magyarázat (????)
Megpróbálom elmagyarázni (nem lesz könnyű). Legyen először a szó abcd. Futtassuk le erre az algoritmust! Ugye a szó végéről kezdjük, és előre haladunk. A result értékek sorban: 0, 1, 3, 7, 15. Leírom úgy is, hogy az éppen vizsgált betű alá írom a resultot:

        | a | b | c | d | a ciklus előtt|

--------+---+---+---+---+---------------+

result: | 15| 7 | 3 | 1 | 0             |

Ebből látható, hogy result mindig a már vizsgált postfix D-komplexitását tartalmazza a ciklusmag végén. (Azt már megbeszéltük, hogy ebben az esetben ez 2^postfixhossz - 1.) Persze ezen nem nagyon csodálkozunk, mert mi történik? Mondjuk, hogy ott tartunk, hogy a c-t már vizsgáltuk, most jön a b, és a result 3, mert az utolsó két betűből háromféle részsorozatot lehet alkotni, azaz:

        | a | b | c | d | a ciklus előtt|

--------+---+---+---+---+---------------+

result: |   |   | 3 | 1 | 0             |

Ha hozzávesszük a b-t a vizsgálódáshoz, akkor most hány részsorozatunk lesz? Megmarad az eddigi 3. Ezek elé betehetünk egy-egy 'b'-t, így újabb 3 részsorozatot kapunk és végül van egy olyan részsorozat, hogy 'b'. Tehát az új result érték: 2*result+1=7.

        | a | b | c | d | a ciklus előtt|

--------+---+---+---+---+---------------+

result: |   | 7 | 3 | 1 | 0             |

A probléma akkor kezdődik, ha vannak egyforma betűk a sorozatban. Mondjuk dbabc esete

        | d | b | a | b | c |a ciklus előtt|

--------+---+---+---+---+---+--------------+

result: |   |   | 7 | 3 | 1 | 0            |

eddig minden rendben, de most egy olyan betű jön (b), amivel már találkoztunk. Hány részsorozatunk lesz az utolsó 4 betűből? Megmarad az eddigi 7, hozzáteszünk mindegyikhez előlről egy-egy b-t, ez újabb 7. Számoltunk-e valamit kétszer? Igen: a 'bc'-t, mert az eddigi 7 részsorozatban a 'c' és 'bc' is szerepel, így 'c'-t előlről kiegészítve b-vel 'bc'-t már kétszer számoljuk. Ebből adódik (és ez az, amit nehéz látni), hogy le kell vonnunk a b utolsó előfordulásától jobbra levő result részeredményt (azaz 1-t jelen esetben), ugyanis pontosan ennyi részsorozat elé írhatjuk bármelyik b-t, így ennyit számolunk kétszer.

        | d | b | a | b | c |a ciklus előtt|

--------+---+---+---+---+---+--------------+

result: |   | 13| 7 | 3 | 1 | 0            |

és a vége:

        | d | b | a | b | c |a ciklus előtt|

--------+---+---+---+---+---+--------------+

result: | 27| 13| 7 | 3 | 1 | 0            |

Hát ennyi. Nehéz megérteni, tudom. Fórumon elmagyarázni még ennél is nehezebb. Viszont abban remélem egyet értünk, hogy az algoritmus rövid és piszokgyors. Korántsem exponenciális! Kár, hogy nem gondolkodott rajta igazán senki.

Encsé