Technology Sharing

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

Title

Given a string $s$,character $a,b$, ask the string $s$ How many$a$ beginning$b$ Ending substring.

Problem Solving

20pts

Use a double loop to enumerate the left and right endpoints and determine whether $a$ beginning$b$ If it is a string that ends with , then the answer increases by one.

100pts

The data range is large, so we need to control the time complexity to $O(n\log n)$ Within.

Law 1

We need to find all $a$ beginning$b$ End of the string, then we can for each character$b$, go and see $b$ There are several on the left$a$, then these $a\dots b$ is a legal string. Count the number of characters to the left of a certain position$a$, we can usePrefix andThe algorithm is maintained.

Method 2

We can traverse the entire string, for each $a$ There are several characters to the right of the character$b$, then these $a\dots b$ All are legal strings. Count the characters after a certain position$b$ The number ofSuffix andThe algorithm is maintained.

#include 
                                   

                    上一篇
                    下一篇