[HDU4763]Theme Section(KMP)

发布于 2018-02-21  8 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[HDU4763]Theme Section(KMP)

Description

It's time for music! A lot of popular musicians are invited to join us in the music festival. Each of them will play one of their representative songs. To make the programs more interesting and challenging, the hosts are going to add some constraints to the rhythm of the songs, i.e., each song is required to have a 'theme section'. The theme section shall be played at the beginning, the middle, and the end of each song. More specifically, given a theme section E, the song will be in the format of 'EAEBE', where section A and section B could have arbitrary number of notes. Note that there are 26 types of notes, denoted by lower case letters 'a' - 'z'.
To get well prepared for the festival, the hosts want to know the maximum possible length of the theme section of each song. Can you help us?

Http

HDU

Tag

KMP

题目大意

给出一个字符串,求最长的满足\(ABACA\)形式的串\(A\)的长度

解决思路

由于要求首尾都是\(A\),那么必然要满足前后缀相同,\(KMP\)求出\(Next\)数组后,由于要满足结尾,那么可以从结尾开始跳\(Next\),标记出所有与结尾后缀相同的所有前缀,同时注意,这些标记出来的子串长度不能超过\(\frac{n}{2}\),要不然就会有重复了。再从这些标记了的前缀出发,寻找某一个它能包含的前缀,并满足长度不会使三个字符串重叠。这样就找到了一组三个不重叠的相同子串。取最大长度即可。

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[HDU4763]Theme Section(KMP)


HNCJ OIer 一枚