欢迎光临
我们一直在努力
        找回密码
当前位置：171主机测评 > 服务器技术 > 正文

字符串学习笔记1

2026-07-17 分类：服务器技术 阅读(28) 评论(0)

Manacher

它是干什么的

他是用来匹配回文串的，顾名思义就是用 O(n) 的时间复杂度匹配出最长回文串。

它怎么做的

暴力

首先我们知道暴力的写法，就是用 O(n^2) 的时间复杂度从每个节点暴力向外扩张，Manacher 解决的就是避免重复。

正解

核心思想是利用回文的对称性，避免重复计算。 可以处理奇回文和偶回文，通过插入分隔符统一处理。

1. 在字符串每两个字符之间及两端插入特殊字符（如 #），将奇偶回文统一为奇回文。

统一为奇回文为的是方便计算因为偶回文不太好统计。 2. 维护当前最右回文的中心 mid 和右边界 r。 3. 对于位置 i，若 i<r，则利用对称位置 j=2\\times mid-i 的信息初始化。 4. 暴力扩展求出 i 的最长回文半径。 5. 更新 mid 和 r。

正确性

设当前最右回文为以 mid 为中心，右边界为 r 的回文。 对于位置 i < r，设 j=2\\times mid-i 为 i 关于 mid 的对称点。 如果 i + p_j - 1 < r： 以 j 为中心的回文完全包含在以 mid 为中心的回文中。 由对称性，以 i 为中心的回文长度与以 j 为中心相同。 故 p_i=p_j。

如果 i + p_j - 1 \\ge r： 以 j 为中心的回文超出以 mid 为中心的回文范围。 由对称性，i\\sim r 范围内的回文是确定的。 但r 右侧的字符未知，需要暴力扩展。 故 d_i\\ge r-i+1，需要继续扩展。 初始化 p_i = min(p_j, r - i + 1) 恰好覆盖了这两种情况。

由于扩张时只会扩张 n 次，所以时间复杂度是 O(n)。

code：

void manacher(){
n=strlen(s+1);
int m=0;
t[++m]='$';
for(int i=1;i<=n;i++)
t[++m]=s[i],t[++m]='$';\\\\插入特殊字符
int M=0,R=0;
for(int i=1;i<=m;i++){
if(i>R)
p[i]=1;
else
p[i]=min(p[2*M-i],R-i+1);\\\\初始化
while(i-p[i]>0&&i+p[i]<=m&&t[i-p[i]]==t[i+p[i]])
++p[i];\\\\暴力扩张统计答案
if(i+p[i]-1>R)
M=i,R=i+p[i]-1;\\\\更新数值
}
int ans=0;
for(int i=1;i<=m;i++)
ans=max(ans,p[i]);\\\\统计最大回文串
printf("%d",ans-1);
}

题目

P1659 [国家集训队] 拉拉队排练

P4555 [国家集训队] 最长双回文串

P1659

由题意可知，显然每一个和谐群体就是一个长度为奇数的回文串。

用 Manacher 可以求每个位置的回文半径。

因为我们只要求奇数个的回文串，那么显然我们不需要在字符串里添加一些无关字符。

那么我们用Manacher求出以当前位置为中心的最长回文子串长度。

所以我们就会在求的同时搞出最长的 len。

然后根据对称性可知也有长为len\\times 2-1的回文子串，接着我们只需要统计一下就可以了。

注意我们只要奇数个，去掉偶数个。

因为数据范围过大，所以我们要快速幂使得不会爆掉。

code：

int main(){
scanf("%d%d%s",&n,&k,s+1),len=n,manacher();
for(int i=n;i;i–) {
if(i%2==0)
continue;
sum+=cnt[i];
if(k>=sum)
ans=(ans*quickpow(i,sum))%P,k-=sum;\\\\如果你很聪明你会把quickpow的值开_____，否则你只有 15 pts。
else{
ans=(ans*quickpow(i,k))%P,k-=sum;
break;
}
}
if(k>0)
ans=-1;
cout<<ans;
}

P4555

就直接维护一个 l_i 表示从 i 出发往前的回文串最大长度，维护一个 r_i 表示从 i 出发往后的回文串最大长度，统计答案时直接把每个位置上的答案取最大值即可。

code：

void manacher(){
int m=0,M=0,R=0;
n=strlen(s+1),t[++m]='$',t[0]='@';
for(int i=1;i<=n;i++)
t[++m]=s[i],t[++m]='$';
for(int i=1;i<=m;i++){
if(i<R)
p[i]=min(p[2*M-i],R-i+1);
else
p[i]=1;
while(t[i-p[i]]==t[i+p[i]])
++p[i];
if(i+p[i]-1>R)
M=i,R=i+p[i]-1;
l[i+p[i]-1]=max(l[i+p[i]-1],p[i]-1);
r[i-p[i]+1]=max(r[i-p[i]+1],p[i]-1);
}
for(int i=3;i<=m;i+=2)
r[i]=max(r[i],r[i-2]-2);
for(int i=m;i>=3;i-=2)
l[i]=max(l[i],l[i+2]-2);
int ans=0;
for(int i=3;i<=m;i+=2)
if(r[i]&&l[i])
ans=max(ans,l[i]+r[i]);
cout<<ans;
}

如果你 WA on #12，#13，可以看看这个帖子。

KMP

我已经发过一遍博文了，详见这里。

exKMP(Z函数)

它是干什么的

能在 O(n+m) 的时间内处理出文本串 a 的所有后缀和模式串 b 的最长公共前缀。

其中 n 和 m 分别表示 a 和 b 的长度。

它怎么做的

暴力

你就要用 O(nm) 的时间复杂度依次枚举。

正解

我们首先称最长公共前缀的前面部分为前半段，后面部分为后半段。

以 abcabc 为例，当 i=4 时，abc=abc，前半段为第 1,2,3 个字符组成的 abc，后半段为第 4,5,6 个字符组成的 abc。

我们记录下 p 为使得后端右端点最右的 i。

最长公共前缀是有对称性的。如上例 abcabc，1 对应 4，2 对应 5，3 对应 6。假设 d 的最右端点大于等于 i，我们找到此时 i 的对应点 i'，此时：

  • 若 i' 的后半段右端点已经超过 p 前半段的右端点，此时我们无法利用全部部分，只能利用 i'\\sim z_d 这一段部分的相等性。此时令 z_i=z_d-{i}'+1。
  • 若 i' 后半段右端点未超过 p 前半段的右端点，则可以直接令 z_i={z_i}'。

然后我们暴力扩展至无法计算结束。所以本算法其实只有三步：

  • 根据当前 p 得到一部分长度。
  • 暴力扩展，得到 z_i​。
  • 更新 p。

    • 正确性

    每次暴力扩展必会引起最右端点的右移，没有引起右移则只会操作 1 次，因此时间复杂度 O(n)。

    模板题code:

    void Z(){
    int l=0,r=0;
    z[1]=m;
    for(int i=2;i<=m;i++){
    if(i<=r&&z[i-l+1]<r-i+1)
    z[i]=z[i-l+1];
    else{
    z[i]=max(0ll,r-i+1);
    while(i+z[i]<=m&&b[z[i]+1]==b[i+z[i]])
    z[i]++;
    }
    if(i+z[i]-1>r)
    l=i,r=i+z[i]-1;
    }
    }

    void work(){
    int l=0,r=0;
    for(int i=1;i<=n;i++){
    if(i<=r&&z[i-l+1]<r-i+1)
    p[i]=z[i-l+1];
    else{
    p[i]=max(0ll,r-i+1);
    while(i+p[i]<=n&&p[i]<m&&b[p[i]+1]==a[i+p[i]])//如果你是 7 pts 那么有可能是这打错了
    p[i]++;
    }
    if(i+p[i]-1>r)
    l=i,r=i+p[i]-1;
    }
    }

    signed main(){
    cin>>(a+1)>>(b+1),n=strlen(a+1),m=strlen(b+1),Z(),work();
    for(int i=1;i<=m;i++)
    ans^=1ll*i*(z[i]+1);
    cout<<ans<<endl,ans=0;
    for(int i=1;i<=n;i++)
    ans^=1ll*i*(p[i]+1);
    cout<<ans;//十年OI一场空，不开_____见祖宗
    }

    题目

    P2375

    CF526D

    P2375

    我们用 Z 函数求出每个后缀与原串的 lcp，然后很轻松的利用差分统计答案即可。Z 函数可以在O(N)的时间内求出每个后缀与原串的 lcp，他类似于马拉车算法，也是递推地求解。

    假设我们要求第 i 个后缀的 lcp，我们已经求出来前 i-1 个，维护匹配 lcp 一个最右端的指针，记此时的后缀为 pos，原串为 s。pos+lcp_{pos}-1 是 max(j+lcp_j-1) {j<i} 那么我们可以发现i如果位于 pos+lcp_{pos}-1 的左面的话，我们可以利用之前的结果更新当前的 lcp，然后再暴力扩展，随时更新一下指针，和 Manacher 其实是一个道理。

    void solve(){
    memset(lcp,0,sizeof lcp),memset(t,0,sizeof t),pos=r=0,ans=1,cin>>(s+1),len=strlen(s+1);
    for(int i=2;i<=len;++i){
    if(pos==0){
    int p=1;
    while(s[p+lcp[i]]==s[i+lcp[i]])
    ++lcp[i];
    if(lcp[i])
    r=i+lcp[i]-1,pos=i;
    continue;
    }
    if(i>r){
    int p=1;
    while(s[p+lcp[i]]==s[i+lcp[i]])
    ++lcp[i];
    if(lcp[i])
    r=i+lcp[i]-1,pos=i;
    continue;
    }
    int npos=i-pos+1;
    lcp[i]=min(lcp[npos],r-i+1);
    while(s[lcp[i]+1]==s[i+lcp[i]])
    ++lcp[i];
    if(i+lcp[i]-1>r)
    r=i+lcp[i]-1,pos=i;
    }
    for(int i=2;i<=len;++i)
    if(lcp[i])
    t[i]++,t[min(2*(i-1),min(len,i+lcp[i]-1))+1]–;
    for(int i=1;i<=len;++i)
    t[i]+=t[i-1];
    for(int i=1;i<=len;++i)
    ans=ans*(t[i]+1)%mod;
    cout<<ans<<endl;
    }

    CF526D

    这道题我们可以利用 KMP 的性质来做，我们直接上推算过程：

    首先我们可以把 AB 分为名为 C 的一组，那么字符串可以变成 CC…CA，其中 C 有 k 个，且 A 是 C 的前缀（由定义而知）。

    求 nxt 数组来扫一遍。首先，在第一个 C 内，所指向的 nxt 都是最开始的地方。第一个 C 结束的地方为临界点。

    当扫到第二个 C 的时候，所指向的 nxt 刚好是第一个 C 里的相同位置。第二个 C 扫描结束后，所指向的 nxt 刚好扫完第一个 C。

    以此类推，后面每次扫到的都是上一个 C 内的相同位置。扫到最后一个点，也就是最后的 A 结束时，它指向了最后一个 C 内的同一位置。

    我们可以通过最后一个点和它的 nxt 指向的地方相减得到 C 的长度，再通过总长和 C 的长度确定 C 的个数和 A 的长度，只要段数是 k 且 A 的长度在 C 以内就可以了。

    但是！

    我们的段数是大于 k 的，本来是有解，我们的程序把它判定为无解了。怎么办呢？

    我们可以先把它原本多少段先求出来，然后看看究竟是 C 的数量除以 k 大，还是模 k 大，就可以判断了。

    code：

    while(i<n){
    if(j==-1||s[i+1]==s[j+1])
    i++,j++,nxt[i]=j;
    else
    j=nxt[j];
    }
    for(int i=1;i<=n;i++){
    p=i-nxt[i],h=i/p;
    if(i%p)
    cout<<((h/m-h%m)>0);
    else
    cout<<((h/m-h%m)>=0);
    }

    最小表示法

    它是干什么的

    它怎么做的

    暴力

    枚举循环同构串的第一个位置，然后暴力用字符串挨个比较的方法比较。

    时间复杂度 O(n^2) 获得 30 分。

    正解

    先将给定字符串 s，我们先把 s 复制粘贴一份在 s 后面，这样得到的新字符串 s1​ 中任意长度为 n 的字串都与 s 循环同构。

    然后用双指针维护，两个指针 i,j 分别表示当前两种答案的开始位置，然后枚举字串的长度 k，当它们前 k-1 个字符均相等，即

    s_{i...i+k-1}=s_{j...j+k-1}

    此时，如果 s_i+k<s_j+k​，那么说明以 j 开头的答案不优，直接 j+1，否则 i+1。

    注意：如果 i=j 那么 j+1，因为要保证我们是对不同的方案比较。

    当 s_i+k<s_j+k​ 且前 k-1 个字符均相同时，我们认为以 j 开头的答案不优，直接 j+1，但是此时对于任意下标 l 满足 l\\in [j,j+k] 都不会是答案。因为一定存在对应的下标 r\\in [i,i+k]， 比以 l 为下标的答案更优。归根结底，就是因为 s_i+k<s_j+k。根据这个原理，我们可以更快速的查找答案。

    正确性

    时间复杂度：O(n)，无需证明。

    题目

    找不到，因为只有模板题…

    如果你有的话你可以在讨论区提出，我会万分感谢。

    后记

    这次主要讲的是较简单字符串专题，我给出的那几道题建议全部独立完成，如果你还有其他好题，欢迎在讨论区提出。

    下次我会将几个自动机讲一下。

    对了，你们来猜一下我是几年级，答案会使你惊讶，假设你看了 1\\div 0=? 那篇文章的话。

    您的肯定是我坚持的动力。

    赞(0)
    未经允许不得转载：171主机测评 » 字符串学习笔记1
    分享到： 更多 (0)
    标签：

    相关推荐

    评论 抢沙发

    取消

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址

    热门标签

    #人工智能(57872)#python(19708)#开发语言(16579)#java(15224)#运维(15156)#linux(14785)#大数据(14344)#服务器(12909)#算法(11615)#前端(10692)#网络(9218)#数据库(8755)#ai(8662)#c++(8059)#课程设计(6759)#学习(6645)#机器学习(6613)#区块链(5844)#OpenClaw(5378)#后端(5065)#spring boot(4959)#深度学习(4846)#c语言(4326)#毕业设计(4277)#数据结构(4150)#安全(3949)#docker(3894)#架构(3771)#javascript(3763)#大模型(3597)

    热门文章

    最新文章

    归档

    分类