牛牛和字符串的日常时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述牛牛每天都要做的事就是读书从书里找自己喜欢的句子他每天都会去读一本书如果牛牛今天读的书的某连续k kk个字符刚好是牛牛喜欢句子的某个前缀那么牛牛将得到k kk点兴奋感但他每天只能注意到一次自己喜欢的句子也就是每天只能增加一次兴奋感也就是说他会尽量去找那个让自己兴奋度增加最多的句子那么n nn天之后牛牛总共最多能有多少兴奋感输入描述第一行是一个字符串s ∣ s ∣ 1 × 10 5 s∣s∣1×10^5s∣s∣1×105表示牛牛喜欢的字符串第二行是一个整数n nn表示总共经历了n nn天 n 100 n100n100接下来n nn行每行一个字符串t i ∣ t i ∣ 1 × 10 5 t_i∣t_i∣1×10^5ti​∣ti​∣1×105分别表示牛牛第i ii天读的书输出描述输出这n天来牛牛最大能获得的兴奋感示例1输入abcdefg 3 adcabc xyz abdefg输出5说明第一天有 a , a b c a,abca,abc可以增加兴奋度选择 a b c abcabc第二天没有第三天有 a b abab总共为5 55解题思路本题是KMP模式匹配的拓展应用核心是对每日的文本串求解其与目标前缀串的最长匹配长度通过KMP算法在线性时间内完成所有文本的匹配计算。1. 问题等价转化每天的最大兴奋值等价于在当日文本串t tt的所有连续子串中能与喜欢的字符串s ss的前缀匹配的最大长度。例如s a b c d e f g sabcdefgsabcdefg文本串中出现子串abc对应前缀长度3出现ab对应长度2每天取最大值计入总兴奋度即可。2. 算法选型KMP字符串匹配暴力逐一枚举子串的时间复杂度为O ( ∣ s ∣ × ∣ t ∣ ) O(|s| \times |t|)O(∣s∣×∣t∣)在十万级字符规模下会超时。KMP算法通过预处理模式串的前缀函数将单次匹配优化为线性时间完美适配本题数据规模。前缀函数next数组对于模式串s ssnxt[i]表示s ss的前i ii个字符组成的子串其最长相等真前缀与真后缀的长度。作用是匹配失败时快速回退匹配指针避免重复比对已匹配的字符。匹配过程遍历文本串的每个字符维护当前匹配长度j jj若当前字符与模式串对应位置匹配匹配长度j jj加1若不匹配利用next数组回退到最长可匹配的前缀位置直到匹配成功或回退到起点全程记录匹配长度j jj的最大值即为当日的最大兴奋值。3. 整体执行流程预处理模式串s ss计算得到next数组。对每天的文本串执行KMP匹配记录当日最大匹配长度。将所有天的最大长度累加得到总兴奋度。4. 复杂度分析预处理next数组时间复杂度O ( ∣ s ∣ ) O(|s|)O(∣s∣)单日文本匹配时间复杂度O ( ∣ t i ∣ ) O(|t_i|)O(∣ti​∣)总时间复杂度O ( ∣ s ∣ ∑ ∣ t i ∣ ) O(|s| \sum|t_i|)O(∣s∣∑∣ti​∣)总字符量在十万级到百万级完全适配1秒时间限制。总结核心逻辑将每日最大兴奋值转化为文本串与模式串的最长前缀匹配长度通过KMP算法线性完成匹配全程记录匹配长度的最大值逐日累加得到最终结果。关键操作前缀函数预处理、KMP匹配指针回退、实时更新最大匹配长度。效率保障线性时间复杂度无冗余比对十万级字符可毫秒级处理完成。代码简要说明快读函数read快速读取整数天数提升大规模数据下的输入效率。前缀函数计算模式串从下标1开始存储初始化匹配指针j0。遍历模式串遇到字符不匹配时通过nxt[j]回退指针匹配成功则j自增并赋值给nxt[i]。每日匹配逻辑读入当日文本串初始化匹配指针j0、当日最大值res0。遍历文本串每个字符按KMP规则更新匹配指针j同步更新res为历史最大匹配长度。若匹配到完整模式串j等于模式串长度执行回退nxt[j]继续处理后续字符保证后续匹配正确。将当日最大值累加到总答案ans。结果输出所有天数处理完成后输出总兴奋度ans。下标设计字符串统一从1开始索引适配KMP经典实现方式边界处理更简洁直观。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;llread(){ll x0,f0;charchgetchar();while(!isdigit(ch)){if(ch-)f1;chgetchar();}while(isdigit(ch)){xx*10ch-0;chgetchar();}returnf?-x:x;}constll MAXN100000100;charch[MAXN],s[MAXN];ll ans,nxt[MAXN],n,m;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf(%s,ch1);nstrlen(ch1);for(ll i2,j0;in;i){while(jch[j1]!ch[i])jnxt[j];if(ch[j1]ch[i])j;nxt[i]j;}mread();while(m--){scanf(%s,s1);ll lenstrlen(s1);ll res0;for(ll i1,j0;ilen;i){if(jch[j1]!s[i])jnxt[j];if(ch[j1]s[i])j;resmax(res,j);if(jn)jnxt[j];}ansres;}printf(%lld\n,ans);return0;}