logo AlgoBeat OnlineJudge
登录 注册

#216742. 远古卷轴

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

:::info[题目背景]

战斗仍在继续。

「沉星书库」深处的大厅早已看不出原本的模样。 断裂的石柱横倒在地,古老书架在魔力冲击中化作焦黑的碎片,四处飞散的尘埃与纸页在紊乱的气流里翻卷,仿佛一场无声燃烧的雪。 黑色的冲击一次又一次撕裂地面,又被更耀眼的魔法正面截断;轰鸣声在穹顶下层层回荡,震得人几乎连呼吸都无法平稳下来。

即使有了聚魔石的支撑,局面也依旧没有轻易好转。

那头盘踞在书库中的魔物实在太强了。 它像是早已与此地残存的古老魔力融为一体,越是久战,气息便越发沉重而危险。 菲伦的普通攻击魔法只能勉强维持局势不至于彻底崩塌,休塔尔克也几次试图逼近,却都被对方扩散出的恐怖压迫硬生生逼退回来。 至于芙莉莲,虽然仍旧站在最前方,神色也没有太大变化,但那种迟迟无法将战局拉向终结的僵持,本身就已经足够说明问题。

又一次术式碰撞之后,短暂的间隙终于出现了。

芙莉莲轻轻向后退了半步,银白色的发梢在尚未平息的余波里微微飘起。 她抬起眼,望着高台前方那头仍在缓慢逼近的魔物,目光里第一次浮现出一点若有所思的意味,像是终于从记忆中翻找到了某个尘封已久的答案。

「这样下去,会很麻烦呢。 」她轻声说道。

「还有别的办法吗?」菲伦立刻问。

芙莉莲没有马上回答,只是伸手探入法袍内侧,取出一卷已经十分陈旧的远古卷轴。 卷轴边缘泛着暗黄,封口处的纹样早已磨损得模糊不清,只有最中央那道极古老的术式印记,仍旧透出一种沉静而危险的气息。 那不像是寻常战斗中会被随手使用的魔法,更像是从很久很久以前遗留下来的东西,安静地沉睡在岁月深处,直到此刻才再次被人唤醒。

「这是我以前收集到的一种古代术式。 」芙莉莲平静地说道,「对付这种类型的魔物,应该很有效。 」

休塔尔克望着那卷卷轴,神情却没有轻松多少:「既然这么有效,为什么不一开始就用?」

「因为没那么简单。 」芙莉莲轻轻展开卷轴,低头看了一眼上面复杂而古老的术式文字,「这个魔法本身并不难控制,麻烦的是,想让它发挥出最佳的功效,需要动点脑子。 」

「动点脑子?」菲伦微微一怔。

「嗯。 」芙莉莲点了点头,「古代魔法使总喜欢把关键术式设计成这样。 不同的术式组合能引出不同强度的魔法,组合不好这些术式的话,终究还是打不过的;然而如果能组合好的话,能发挥出真正的远古魔法之力。 」

她的声音依旧平静,可前方那头魔物显然不会体贴地为他们留出太多思考时间。 漆黑的魔力再次在大厅深处汇聚,像风暴来临前不断下压的乌云。 菲伦下意识握紧法杖,休塔尔克也重新站稳脚步,挡在两人身前。 而芙莉莲则低头看着卷轴上逐渐浮现的术式纹路,像是在确认某些极其细微、却又绝不能弄错的条件。


远古卷轴可以看作一条很长的纸带,上面写着一个只包含小写英文字母的字符串 ,长度为

为了最好地发挥出卷轴上远古魔法的威力,芙莉莲需要从这条纸带上挑出恰好 段内容完全相同的连续片段。设被挑出的内容是字符串 ,这 次出现的起始位置分别是

段可以互相重叠;只要它们在卷轴上的内容完全相同,就算是合法选择。同一个字符串出现在不同位置,算不同的出现。

术式重叠度越高,则能造成的威力越大,芙莉莲定义了「术式叠印得分」为:

  • 先把这 段片段的长度全部加起来,得到术式叠印长度
  • 再看原卷轴上覆盖这 段片段的最短连续区间。这个区间从第一个被选中的片段开头开始,到最后一个被选中的片段结尾结束,得到卷轴长度

于是,这组选择的「术式叠印得分」为

如果芙莉莲觉得所有方案都不划算,也可以什么都不选,此时「术式叠印得分」记为

请你求出最大可能的「术式叠印得分」。

输入格式

输入第一行包含两个整数 ,代表卷轴上字符串 的长度和芙莉莲想挑出的段数。

输入第二行包含一个长度恰好为 的字符串 ,只包含小写英文字母。

输出格式

输出一行一个整数,表示最大可能的「术式叠印得分」。

样例

样例输入 1

7 3
abababa

样例输出 1

2

样例输入 2

5 3
aaaaa

样例输出 2

4

样例输入 3

7 4
abacaba

样例输出 3

0

数据范围与提示

对于样例一,可以选择的片段为 aba,位置分别为,术式叠印长度为 ,卷轴长度为 ,则此时「术式叠印得分」为 ,可以证明没有更优的选择。

对于样例二,可以选择的片段为 aaa,位置分别为 ,术式叠印长度为 ,卷轴长度为 ,则此时「术式叠印得分」为 ,可以证明没有更优的选择。

对于样例三,可以选择的片段为 a,位置分别为 ,术式叠印长度为 ,卷轴长度为 ,此时则「术式叠印得分」为,显然这个方案并不划算,芙莉莲可以选择什么都不选,则「术式叠印得分」为

:::info[题目背景]


古老卷轴上的最后一道纹路终于彻底亮起。

那一瞬间,原本被黑色魔力与轰鸣填满的大厅,像是忽然被某种更久远、也更沉静的力量按住了。淡金色的光从卷轴表面缓缓扩散开来,沿着芙莉莲的法杖一寸寸流入已经构筑完成的术式之中。那并不是炫目到令人无法直视的光辉,反而安静得近乎肃穆,像某种自漫长岁月彼端降临的回响。可正是这样的力量,让那头魔物第一次真正停滞了一瞬。

「就是现在。」芙莉莲轻声说道。

菲伦立刻抬手,将最后一股聚魔石中的魔力稳稳送入大量的普通攻击魔法;休塔尔克也咬紧牙关,从侧面强行逼近,用尽全力牵制住那头魔物的动作。下一刻,芙莉莲展开的远古魔法彻底落下。庞大而凝练的术式光辉在大厅中央收束成一道近乎笔直的辉线,毫无迟疑地贯穿了那团盘踞已久的黑暗。

没有凄厉的哀鸣,只有一声低沉而漫长的震响。那头魔物胸口暗红色的核心在光辉中寸寸崩裂,漆黑的外壳也随之剥落、瓦解,像风化了数百年的石像终于迎来彻底崩塌。紊乱的气流卷起满地碎纸与石尘,书架残骸在余波中微微震颤,随后,一切都慢慢安静了下来。

大厅里只剩下急促却逐渐平稳的呼吸声。

菲伦放下法杖,指尖还残留着轻微的颤抖;休塔尔克撑着武器站稳身形,长长吐出一口气,仿佛直到此刻才终于确认战斗已经结束。芙莉莲则只是安静地看着前方那片正在散去的黑色残渣,神情依旧平静,像是终于处理掉了一件稍显麻烦的旧事。

「结束了呢。」她轻声说。

短暂整理过行装之后,三人没有在原地停留太久。破碎的大厅后方,一道通往更深处的回廊已经在昏暗中静静显现出来。那里没有风,也没有声音,只有古老石壁之间沉默流淌的微弱魔力。