标签：复健 loc int KMP fail ans week1 border

复健week1

主要是字符串基础，都是以前做过的题。

KMP

LG3375 【模板】KMP

唯一没忘的东西，原理理解后比较简单，懒得详细写了。

复杂度证明：\(j\) 指针至多加 \(n\) 次，无法匹配后也至多回退 \(n\) 次。复杂度 \(O(n)\)

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;
}
for(int i=1,j=0;i<=m;++i){
    while(j&&t[i]!=s[j+1])j=nxt[j];
    if(t[i]==s[j+1])++j;
    if(j==n)printf("%d\n",i-n+1);
}

CF1200E Compress Words

sol1

设需要合并第 \(i\) 个字符串，长度为 \(len\)，只需求目前已经得到答案串的后 \(len\) 位的后缀与 \(s_i\) 的前缀的最长匹配长度。这个可以做到 \(O(len)\)。既可以先求 \(s_i\) 的 \(border\) 然后让 \(s_i\) 与 \(ans\) 匹配（24.09.05），也可以直接让 \(s_i\) 和 \(ans\) 后 \(len\) 位拼在一起直接求 \(border\)（21.10.25）。总复杂度 \(O(n)\)

scanf("%d",&n);
scanf("%s",ans+1);top=strlen(ans+1);
for(int T=2;T<=n;++T){
    scanf("%s",s+1);m=strlen(s+1);
    int len=min(top,m);
    for(int i=1;i<=len;++i)t[i]=ans[top-len+i];
    kmpself();int j=0;
    for(int i=1;i<=len;++i){
        while(j&&s[j+1]!=t[i])j=nxt[j];
        if(s[j+1]==t[i])++j;
    }
    for(int i=j+1;i<=m;++i)ans[++top]=s[i];
}
printf("%s",ans+1);

sol2

还可以二分加字符串哈希，比较好理解。不过这个哈希貌似要能做到快速求一段字符串的哈希值，因此可能需要多重哈希。我的想法是用一个前缀异或，一个前缀和，一个前缀积，可能可以保证正确率。懒得写了。

LG4824 [USACO15FEB] Censoring S

模式串 \(s\)，文本串 \(t\)。匹配时记录一下对于 \(t\) 的每一位 \(s\) 匹配了多少位，然后若 \(s\) 匹配完成则从不在这次匹配的 \(t\) 位置开始，可以用一个栈维护答案（感觉栈应该是最好写的）。

LG3435 [POI2006] OKR-Periods of Words

容易发现对于每一个前缀，只需要求出其最短 \(border\) 即可。然后不可能每次都跳 \(fail\)，可以类似并查集优化一下。

for(int i=2,j=2;i<=n;++i,j=i){
    if(nxt[j]){
        j=nxt[j];
        if(nxt[j])j=nxt[j];//j<i，由于之前已经优化过了，这次可以直接定义到最小border
    }
    if(nxt[i])nxt[i]=j;//直接将nxt[i]定义为最短的border，这样以后可以更快找
    ans+=i-j;
}

LG2375 [NOI2014] 动物园

一个直观的想法就是直接跳 \(fail\) 直到 \(border\) 长度小于等于目前子串的 \(\frac{1}{2}\)，然后答案统计就是这个 \(border\) 的 \(border\) 有多少个，这个可以转移。然而如果这样朴素地执行对于 aaaa...a 这种串显然会 TLE。其实只需要跑一次 KMP 求出答案，然后再跑一次限制 \(border\) 长度的 KMP 即可找到需要定位的 \(border\)，然后直接用第一次 KMP 的答案即可。

manacher

非常好奇当年是怎么花费了一个下午还没学懂的。只要记住几个和 Z 函数非常相似的定义就好理解了。\(maxr\)：已找到的回文串的最远右侧位置。\(loc\)：取到 \(maxr\) 的回文串的中心。然后 \(ext_i\) 表示以 \(i\) 为中心的回文串的向一边延申的长度。

容易发现这个 \(ext_i\) 的定义只能解决长度为奇数的字符串，中间插板即可。注意不要插成 a|a|a|a|a，而要插成 |a|a|a|a|，不然单独的一个 a 没法判断。

复杂度证明：\(mxr\) 指针最多向右移动 \(n\) 次，\(ext\) 被 \(mxr\) 限制。

模板：LG3805。双倍经验：LG1723

inline void manacher(){
	for(int i=1,loc=0,mxr=0;i<=n;++i){
		ext[i]=min(mxr-i+1,ext[2*loc-i]);
		while(s[i+ext[i]]==s[i-ext[i]])++ext[i];
		if(i+ext[i]-1>=mxr)mxr=i+ext[i]-1,loc=i;
	}
}

int main(){
	int T;scanf("%d",&T);
	while(T--){
		scanf("%s",t+1);m=strlen(t+1);
		s[0]='%';
		for(int i=1;i<=m;++i)s[2*i-1]='|',s[2*i]=t[i];
		n=2*m+1;s[n]='|',s[n+1]='*';
		manacher();
		int maxv=0;
		for(int i=1;i<=n;++i)maxv=max(maxv,ext[i]-1);
		printf("%d\n",maxv);
	}	
	return 0;
}

LG5446 [THUPC2018] 绿绿和串串

不难，在细节上栽跟头比较多，直接看代码算了

//插板省略
manacher();
for(int i=1;i<=m;++i)len[i]=(ext[2*i]-1)/2;
for(int i=m;i>=1;--i){
    if(i+len[i]>=m)ans[i]=1;
    else if(i+len[i]<=m&&ans[i+len[i]]&&i==len[i]+1)ans[i]=1;
}
for(int i=1;i<=m;++i)//i要从1开始，自作聪明了属于是
    if(ans[i])printf("%d ",i);
puts("");
memset(ans,0,sizeof(int)*(m+1));

LG6216 回文匹配

算是 KMP + manacher 的融合题吧。难度主要在计数，其实也不是很难。

考虑对于中心为 \(loc\) 的回文串，左右边界为 \(l,r\)，我们考虑对匹配的左端在 \(l\sim loc-(x+1)/2\) 的字符串计数，答案即为（其中 \(a_i\) 表示左端能否匹配）

\[\sum_{i=l}^{loc-(x+1)/2}a_i\times(i-l+1) \]

优化一下可以得到

\[\sum_{i=l}^{loc-(x+1)/2} (a_i\times i)+ (1-l)\times \sum_{i=l}^{loc-(x+1)/2}a_i \]

维护一下 \(a_i\) 和 \(a_i\times i\) 前缀和即可。

对于右侧同理，特判一下模式串长度为奇数的情况，此时还需考虑模式串的中心和回文串中心对齐时恰好能匹配。

答案对 \(2^{32}\) 取模，调了1h没发现，无语了

const int N=3000006;
int n,m,nxt[N],ext[N];
ll lef[N],rit[N],sml[N],smr[N],dsl[N],dsr[N],ans;
char s[N],t[N];

int main(){
	scanf("%d%d",&n,&m);
	scanf("%s%s",s+1,t+1);
	for(int i=2,j=0;i<=m;++i){
		while(j&&t[j+1]!=t[i])j=nxt[j];
		if(t[j+1]==t[i])++j;
		nxt[i]=j;
	}
	for(int i=1,j=0;i<=n;++i){
		while(j&&t[j+1]!=s[i])j=nxt[j];
		if(t[j+1]==s[i])++j;
		if(j==m)lef[i-m+1]++,rit[i]++;
	}

	for(int i=1,loc=0,mxr=0;i<=n;++i){
		ext[i]=min(ext[2*loc-i],mxr-i+1);
		while(s[i-ext[i]]==s[i+ext[i]]&&i-ext[i]>=1&&i+ext[i]<=n)++ext[i];
		if(i+ext[i]-1>=mxr)mxr=i+ext[i]-1,loc=i;
	}
	for(int i=1;i<=n;++i){
		dsl[i]=dsl[i-1]+lef[i]*i;
		dsr[i]=dsr[i-1]+rit[i]*i;
		sml[i]=sml[i-1]+lef[i];
		smr[i]=smr[i-1]+rit[i];
		//printf("%d %d %d %d\n",sml[i],smr[i],dsl[i],dsr[i]);
	}
	for(int i=1;i<=n;++i){
		ll x=(m+1)/2,l=i-ext[i]+1,r=i+ext[i]-1;
		//printf("%d %lld %lld %lld\n",ext[i],dsl[i-x]-dsl[l-1]+(sml[i-x]-sml[l-1])*(1-l),(smr[r]-smr[i+x-1])*(r+1)-dsr[r]+dsr[i+x-1],(rit[i+m/2]==1&&i+m/2<=r)*(r-i-x+2));
		if(l<=i-x)ans+=dsl[i-x]-dsl[l-1]+(sml[i-x]-sml[l-1])*(1-l);
		if(r>=i+x)ans+=(smr[r]-smr[i+x-1])*(r+1)-dsr[r]+dsr[i+x-1];
		if(m%2==1&&rit[i+m/2]==1&&i+m/2<=r)ans+=(r-i-x+2);
	}
	printf("%lld\n",ans%(1ll<<32));//byd答案取模
	return 0;
}

ACAM

就是 KMP on Trie。直接看代码算了。

int ch[N][26],tot=1,nxt[N],bot[N];//nxt即fail
queue<int>q;
inline void insert(char *s){
    int n=strlen(s+1),u=1;
    for(int i=1;i<=n;++i){
        int w=s[i]-'a';
        if(!ch[u][w])ch[u][w]=++tot;
        u=ch[u][w];
    }++bot[u];
}
inline void build(){
    for(int i=0;i<26;++i)ch[0][i]=1;
    nxt[1]=0;q.push(1);
    while(!q.empty()){
        int u=q.front(),f=nxt[u];q.pop();
        for(int i=0;i<26;++i){
            int v=ch[u][i];
            if(!v){ch[u][i]=ch[f][i];continue;}
            nxt[v]=ch[f][i];
            q.push(v);
        }
    }
}

LG3808 AC 自动机（简单版）

inline int eazy_version_wa(char *s){//统计多少个不同的模式串在文本串中出现过(错误做法)
    int n=strlen(s+1),u=1,ans=0;
    for(int i=1;i<=n;++i){
        int w=s[i]-'a';
        if(ch[u][w])u=ch[u][w];
        else u=ch[nxt[u]][w];
        ans+=bot[u];
    }
    return ans;
}
/*
hack:
2
abaaa
b
abaaa
无法定位到字符串 b，其中 b 对应的节点为 ab 中 b 的 fail
*/
inline int eazy_version(char *s){//统计多少个不同的模式串在文本串中出现过(正确做法)
    int n=strlen(s+1),u=1,ans=0;
    for(int i=1;i<=n;++i){
        int w=s[i]-'a',v=ch[u][w],vv=v;
        while(vv>1&&bot[vv]!=-1){//模式串都是从根开始，因此要定位到这个模式串，要利用fail边
            ans+=bot[vv];
            bot[vv]=-1;
            vv=nxt[vv];
        }
        u=v;
    }
    return ans;
}

LG5357 【模板】AC 自动机

简单版 v2，与这题做法可以相同。

\(u\to fail_u\) 构成了一张有向无环图。因为 \(fail_u\) 为 \(u\) 的一个子串，然后 \(fail_u\) 又能恰好对应一个从根开始的字符串（可能是一个模式串），跑拓扑排序即可求得所有模式串的出现次数。

inline void run_time(char *t){
    memcpy(tmp,ind,sizeof(int)*(tot+1));
    int n=strlen(t+1);
    for(int i=1;i<=tot;++i)
        if(!tmp[i])q.push(i);
    for(int i=1,u=1;i<=n;++i){
        int w=t[i]-'a',v=ch[u][w];
        if(v>1)++val[v];
        u=v;
    }
    while(!q.empty()){
        int u=q.front();q.pop();
        if(lis[u].size()){
            for(auto x:lis[u])
                tim[x]=val[u];
        }
        int v=fail[u];
        val[v]+=val[u];
        --tmp[v];
        if(!tmp[v])q.push(v);
    }
}

LG3121 [USACO15FEB] Censoring G

LG4824翻版，又自己打了一遍练手，没啥难度（但是中间发现函数里面开数组爆了）。

LG3966 [TJOI2013] 单词

额暴力 KMP 匹配可以过，复杂度 \(O(n\sum|T|)\)，没办法，\(n\) 太小了。

可以把这些字符串拼在一起作为文本串，中间插上特殊符号作为分割，然后跑 ACAM。自己又写了一遍，结果又忘记在主函数中建立 ACAM。

杂记

还打了一场 CF div3 和 ABC，表现平平吧，现在还没补题。

周末本来准备多做点题的，至少计划要把写过的 ACAM 的题都搞完。但周六睡过去了，周天又去医院检查了一个上午（这个身体真是越来越差了，不知道这个拉肚子能不能治好，经典身体难受检查屁事没有）。

然后去参加了一下校基地的宣讲，场馆人坐满了后面还站了一排，很闷很热，听到后面脑袋要炸了。那个老师讲了大概 \(50\rm min\)，感觉对这个新生的吸引力蛮大的（但是挺多了估计就挺烦了，就和 sjf 一样），不过宣传片很燃（但是说实话有点意义不明的运镜）。

感觉一周没干什么事，晚上还有活动，下周就开始上课了。

欸晚上活动搞完了，现在已经晚上11点了，先是学生会的一群 GPA 贼高的学长过来分享经验，感觉狠狠地被压力到了；然后又是破冰行动，一堆人坐在草坪上搞活动，对我来说挺坐牢的。byd下午写了个图论还没调出来，真是失败的一天啊。还是看看下周吧

标签：复健,loc,int,KMP,fail,ans,week1,border
From： https://www.cnblogs.com/BigSmall-En/p/18403679

复健week1

复健week1

KMP

LG3375 【模板】KMP

CF1200E Compress Words

sol1

sol2

LG4824 [USACO15FEB] Censoring S

LG3435 [POI2006] OKR-Periods of Words

LG2375 [NOI2014] 动物园

manacher

LG5446 [THUPC2018] 绿绿和串串

LG6216 回文匹配

ACAM

LG3808 AC 自动机（简单版）

LG5357 【模板】AC 自动机

LG3121 [USACO15FEB] Censoring G

LG3966 [TJOI2013] 单词

杂记

相关文章

赞助商

阅读排行