Technologieaustausch

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

Allgemeine Vorstellung vom Thema

gegebene Zeichenfolge $S$,Charakter $A,B$, frag string $S$ Wie viele sind da drin?$A$ Anfang$B$ Der abschließende Teilstring.

Ideen zur Problemlösung

20 Punkte

Verwenden Sie eine Doppelschleife, um den linken und rechten Endpunkt aufzuzählen und festzustellen, ob dies der Fall ist $A$ Anfang$B$ Wenn die Zeichenfolge am Ende die Antwort ist, fügen Sie eine hinzu.

100 Punkte

Der Datenbereich ist groß und wir müssen die zeitliche Komplexität darin kontrollieren $Ö(N\mathrm{sieheG}N)$ Innerhalb.

Fayi

wir müssen alles finden $A$ Anfang$B$ Ende der Zeichenfolge, dann können wir für jedes Zeichen$B$, Geh und sehe $B$ Wie viele sind auf der linken Seite?$A$, dann diese $A\dots B$ Es handelt sich um eine legale Zeichenfolge.Zählen Sie, wie viele Zeichen sich auf der linken Seite einer bestimmten Position befinden$A$, wir können benutzenPräfixsummeDer Algorithmus bleibt erhalten.

Methode 2

Wir können für jeden die gesamte Zeichenfolge durchlaufen $A$ Wie viele Zeichen befinden sich rechts vom Zeichen?$B$, dann diese $A\dots B$ Alle sind legale Zeichenfolgen.Zählen Sie Zeichen ab einer bestimmten Position$B$ Die Nummer kann verwendet werdenSuffixsummeDer Algorithmus bleibt erhalten.

#include 
                                   

                    上一篇
                    下一篇