似乎在梦中见过的样子

一本通·提高篇 · 代码 · cpp · 难度 5/5 · 共 1057 字

枚举起点跑KMP，border链找ABA结构

一本通
练习

正文

// 原题：https://oj.yecheng.tv/p/T1469
// 题意：给串 S 和 k，统计形如 A+B+A 的子串个数，其中 |A|>=k、|B|>=1，同一子串只按位置计一次。
// 思路：枚举起点 l 在后缀上跑 KMP，得到每个长度 len 的最长 border，再沿 border 链取最小的、>=k 的那个，若 2b<len 则该子串合法。
// 复杂度：O(n^2) 时间 / O(n) 空间
// 易错点：前缀函数 p[1] 必须置 0（长度为 1 的串无真 border）；取最小 border 时条件是 p[b]>=k 而非 b>=k 一直跳。
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    if(!(cin>>s)) return 0;
    int k;
    if(!(cin>>k)) return 0;
    int n=(int)s.size();
    long long ans=0;
    vector<int> p(n+1,0);
    int need=2*k+1;
    for(int l=0;l<n;l++){
        if(n-l<need) break;
        p[0]=0;
        if(n>=1) p[1]=0;
        for(int len=2;l+len-1<n;len++){
            int j=p[len-1];
            while(j>0&&s[l+len-1]!=s[l+j]) j=p[j];
            if(s[l+len-1]==s[l+j]) j++;
            p[len]=j;
            if(len>=need){
                int b=j;
                while(b>=k&&p[b]>=k) b=p[b];
                if(b>=k&&2*b<len) ans++;
            }
        }
    }
    cout<<ans<<'\n';
    return 0;
}

似乎在梦中见过的样子

正文

一本通·提高篇的其它内容