搜索

字符串杂题


发布时间: 2022-11-24 22:57:00    浏览次数:31 次

字符串杂题。

P5446 [THUPC2018]绿绿和串串

一个回文中心 \(i\),如果右端点能到字符串末尾,或者左端点能到开头且 \(2i-1\) 合法,则 \(i\) 合法。马拉车乱搞就行了,记得清空。

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char ch[1000010],s[2000010];
int f[2000010];
int n;
bool v[2000010];
int main(){
    int tim;scanf("%d",&tim);
    while(tim--){
        scanf("%s",ch+1);n=2*strlen(ch+1)+1;
        for(int i=1;i<=n;i++){
            if(i&1)s[i]='#';
            else s[i]=ch[i>>1];
        }
        s[0]='~';
        int r=0,mid=0;
        for(int i=1;i<=n;i++){
            if(i<=r)f[i]=min(f[2*mid-i],r-i+1);
            while(s[i+f[i]]==s[i-f[i]])f[i]++;
            if(i+f[i]>r)r=i+f[i]-1,mid=i;
        }
        int len=n>>1;
        for(int i=n-1;i>=1;i-=2){
            int pos=i>>1;
            if(pos+(f[i]-1>>1)==len||(pos-(f[i]-1>>1)==1&&v[2*pos-1]))v[pos]=true;
        }
        for(int i=1;i<=len;i++)if(v[i])printf("%d ",i);
        printf("\n");
        for(int i=1;i<=n;i++)v[i]=false,s[i]=f[i]=0;
    }
    return 0;
}

P3546 [POI2012]PRE-Prefixuffix

首先两个循环相等的串可以被拆成 \(ST,TS\) 的形式。那么 \(S\) 就是 border。问题是怎么求 \(T\)

写一个border子串查询 \(O(\log n)\) 单次找,巨大难写还不知道能不能过

(这玩意怎么写:建SAM后扫描线树剖线段树,详见P4482 [BJWC2018]Border 的四种求法

当然我不会后缀。然后发现 \(S\)\(\left \lfloor \dfrac n2\right\rfloor\) 开始往左右缩小,中间的border似乎有着某种单调性,最多只会扩展 \(1\) 长度,然后就是往下减。那么哈希就行了,整个指针单调扫一遍,复杂度 \(O(n)\)

CF526D Om Nom and Necklace

看到题第一眼找周期,kmp就行了,只要周期整除 \(\left\lfloor \dfrac ik\right\rfloor\)。然后问题是找后面那一小截 \(A\)。这个其实可以直接 Z 函数。合法段可以扩展到 \(s[1\dots n]\)\(s[i\dots n]\) 的 lcp 和 \(|A|\) 的最小值。

CF432D Prefixes and Suffixes

这不板板题吗。不会的参阅oiwiki的kmp的“统计每个前缀的出现次数”部分。

不懂哪里需要 exkmp。

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
#include <random>
#include <cstring>
using namespace std;
char s[100010];
int n,top,nxt[100010],cnt[100010];
void getnxt(){
    for(int i=2,j=0;i<=n;i++){
        while(j&&s[i]!=s[j+1])j=nxt[j];
        if(s[i]==s[j+1])j++;
        nxt[i]=j;
    }
}
pair<int,int>ans[100010];
int main(){
    scanf("%s",s+1);n=strlen(s+1);
    getnxt();
    for(int i=1;i<=n;i++)cnt[nxt[i]]++;
    for(int i=n;i>=1;i--)cnt[nxt[i]]+=cnt[i];
    for(int i=1;i<=n;i++)cnt[i]++;
    int x=n;
    while(x){
        ans[++top]=make_pair(x,cnt[x]);x=nxt[x];
    }
    sort(ans+1,ans+top+1);
    printf("%d\n",top);
    for(int i=1;i<=top;i++)printf("%d %d\n",ans[i].first,ans[i].second);
    return 0;
}

P3538 [POI2012]OKR-A Horrible Poem

又是子串查询border

啊枚举因数能过啊,那没事了。我看这玩意还以为是线性的。

这题枚举因数其实可以直接把所有质因子扫下来然后一个一个除,判是否合法,合法就除掉,不合法不管。

P3426 [POI2005]SZA-Template

一个 \(i\) 长度的前缀合法当且仅当是 border,且 border 树上所有子树节点差的最大值不超过 \(i\) 。树上问题,爆扫就行。

P7456 [CERC2018] The ABCD Murderer

AC 自动机可以求出每个位置结尾的最长的串。这样就变成了经典区间覆盖问题,线段树或者最短路。

免责声明 字符串杂题,资源类别:文本, 浏览次数:31 次, 文件大小:-- , 由本站蜘蛛搜索收录2022-11-24 10:57:00。此页面由程序自动采集,只作交流和学习使用,本站不储存任何资源文件,如有侵权内容请联系我们举报删除, 感谢您对本站的支持。 原文链接:https://www.cnblogs.com/gtm1514/p/16916521.html