牛牛和字符串的日常

时间限制：1秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

牛牛每天都要做的事就是读书，从书里找自己喜欢的句子，他每天都会去读一本书，如果牛牛今天读的书的某连续 $k$ 个字符刚好是牛牛喜欢句子的某个前缀，那么牛牛将得到 $k$ 点兴奋感，但他每天只能注意到一次自己喜欢的句子（也就是每天只能增加一次兴奋感），也就是说他会尽量去找那个让自己兴奋度增加最多的句子，那么，$n$ 天之后牛牛总共最多能有多少兴奋感？

输入描述：

第一行是一个字符串 $s（\mid s\mid <=1\times 10^5）$ 表示牛牛喜欢的字符串

第二行是一个整数 $n$ ，表示总共经历了 $n$ 天 $（n<=100）$

接下来 $n$ 行每行一个字符串 $t_i（\mid t_i\mid <=1\times 10^5）$ ，分别表示牛牛第 $i$ 天读的书

输出描述：

输出这n天来牛牛最大能获得的兴奋感

示例1

输入：

abcdefg
3
adcabc
xyz
abdefg

输出：

5

说明：

第一天有 $"a","abc"$ 可以增加兴奋度，选择 $"abc"$ ，第二天没有，第三天有 $"ab"$ ，总共为 $5$

解题思路

本题是KMP模式匹配的拓展应用，核心是对每日的文本串，求解其与目标前缀串的最长匹配长度，通过KMP算法在线性时间内完成所有文本的匹配计算。

1. 问题等价转化

每天的最大兴奋值，等价于：在当日文本串 $t$ 的所有连续子串中，能与喜欢的字符串 $s$ 的前缀匹配的最大长度。
例如 $s=abcdefg$，文本串中出现子串 abc 对应前缀长度3，出现 ab 对应长度2，每天取最大值计入总兴奋度即可。

2. 算法选型：KMP字符串匹配

暴力逐一枚举子串的时间复杂度为 $O(|s|\times |t|)$，在十万级字符规模下会超时。KMP算法通过预处理模式串的前缀函数，将单次匹配优化为线性时间，完美适配本题数据规模。

• 前缀函数（next数组）：对于模式串 $s$，nxt[i] 表示 $s$ 的前 $i$ 个字符组成的子串，其最长相等真前缀与真后缀的长度。作用是匹配失败时快速回退匹配指针，避免重复比对已匹配的字符。
• 匹配过程：遍历文本串的每个字符，维护当前匹配长度 $j$：
  • 若当前字符与模式串对应位置匹配，匹配长度 $j$ 加1；
  • 若不匹配，利用next数组回退到最长可匹配的前缀位置，直到匹配成功或回退到起点；
  • 全程记录匹配长度 $j$ 的最大值，即为当日的最大兴奋值。

3. 整体执行流程

1. 预处理模式串 $s$，计算得到next数组。
2. 对每天的文本串执行KMP匹配，记录当日最大匹配长度。
3. 将所有天的最大长度累加，得到总兴奋度。

4. 复杂度分析

• 预处理next数组：时间复杂度 $O(|s|)$
• 单日文本匹配：时间复杂度 $O(|t_i|)$
• 总时间复杂度：$O(|s|+\sum |t_i|)$，总字符量在十万级到百万级，完全适配1秒时间限制。

总结

核心逻辑：将每日最大兴奋值转化为文本串与模式串的最长前缀匹配长度，通过KMP算法线性完成匹配，全程记录匹配长度的最大值，逐日累加得到最终结果。
关键操作：前缀函数预处理、KMP匹配指针回退、实时更新最大匹配长度。
效率保障：线性时间复杂度，无冗余比对，十万级字符可毫秒级处理完成。

代码简要说明

1. 快读函数 read：快速读取整数天数，提升大规模数据下的输入效率。
2. 前缀函数计算：
   • 模式串从下标1开始存储，初始化匹配指针j=0。
   • 遍历模式串，遇到字符不匹配时通过nxt[j]回退指针，匹配成功则j自增并赋值给nxt[i]。
3. 每日匹配逻辑：
   • 读入当日文本串，初始化匹配指针j=0、当日最大值res=0。
   • 遍历文本串每个字符，按KMP规则更新匹配指针j，同步更新res为历史最大匹配长度。
   • 若匹配到完整模式串（j等于模式串长度），执行回退nxt[j]，继续处理后续字符，保证后续匹配正确。
   • 将当日最大值累加到总答案ans。
4. 结果输出：所有天数处理完成后，输出总兴奋度ans。
5. 下标设计：字符串统一从1开始索引，适配KMP经典实现方式，边界处理更简洁直观。

代码内容

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<ll>> vvt;
typedef pair<ll,ll> pll;
const ll N=1e3+10;
const ll INF=1e18;
const ll M=1e6+10;
const ll mod=1e9+7;

ll read() {
    ll x = 0, f = 0; char ch = getchar();
    while(!isdigit(ch)) { if(ch == '-') f = 1; ch = getchar(); }
    while(isdigit(ch)) { x = x*10 + ch - '0'; ch = getchar(); }
    return f ? -x : x;
}

const ll MAXN = 100000 + 100;
char ch[MAXN], s[MAXN];
ll ans, nxt[MAXN], n, m;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    scanf("%s", ch + 1);
    n = strlen(ch + 1);
    for(ll i = 2, j = 0; i <= n; i++) {
        while(j && ch[j+1] != ch[i]) j = nxt[j];
        if(ch[j+1] == ch[i]) j++;
        nxt[i] = j;
    }
    m = read();
    while(m--) {
        scanf("%s", s + 1);
        ll len = strlen(s + 1);
        ll res = 0;
        for(ll i = 1, j = 0; i <= len; i++) {
            if(j && ch[j+1] != s[i]) j = nxt[j];
            if(ch[j+1] == s[i]) j++;
            res = max(res, j);
            if(j == n) j = nxt[j];
        }
        ans += res;
    }
    printf("%lld\n", ans);
    return 0;
}