Teknologian jakaminen

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Aiheen yleinen idea

annettu merkkijono $s$,merkki $a,b$, kysy merkkijono $s$ Kuinka monta siellä on$a$ alku$b$ Päättyvä osamerkkijono.

Ideoita ongelmanratkaisuun

20 pistettä

Käytä kaksoissilmukkaa laskeaksesi vasemman ja oikean päätepisteen määrittääksesi, onko se $a$ alku$b$ Merkkijono lopussa on vastaus plus yksi.

100 pistettä

Tietoalue on suuri, ja meidän on säädettävä ajan monimutkaisuus $O(n\log n)$ Sisällä.

Fayi

meidän on löydettävä kaikki $a$ alku$b$ merkkijonon loppuun, voimme jokaisen merkin kohdalla$b$, mene ja näe $b$ Kuinka monta niitä on vasemmalla puolella$a$, sitten nämä $a\dots b$ Se on laillinen merkkijono.Laske kuinka monta merkkiä on tietyn kohdan vasemmalla puolella$a$, voimme käyttääetuliitteen summaAlgoritmi säilyy.

Menetelmä 2

Voimme iteroida koko merkkijonon läpi kullekin $a$ Kuinka monta hahmoa on hahmon oikealla puolella$b$, sitten nämä $a\dots b$ Kaikki ovat laillisia sarjoja.Laske merkit tietyn kohdan jälkeen$b$ Numeroa voidaan käyttääpääte summaAlgoritmi säilyy.

#include 
                                   

                    上一篇
                    下一篇