寒假集训纪要

1.28

KMP算法

匹配

int j;
j=0;
for(int i=1;i<=la;++i)
{
    while(j && b[j+1]!=a[i]) j=next[j];
    if(b[j+1]==a[j]) j++;
    if(j==lb)
    {
        cout<<i-lb+1<<'\n';
        j=next[j];
    }
}

处理 next 数组

j=0;
for(int i=2;i<=lb;++i)
{
    while(j && b[i]!=b[j+1])
        j=next[j];
    if(b[j+1]==b[j]) j++;
    next[i]=j;
}

洛谷模板

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7+50;
int la,lb,next_[N],j;
char a[N],b[N];
signed main()
{
    cin>>a+1;
    cin>>b+1;
    la=strlen(a+1);
    lb=strlen(b+1);
    for(int i=2;i<=lb;++i)
    {
        while(j && b[i]!=b[j+1])
            j=next_[j];
        if(b[j+1]==b[i]) j++;
        next_[i]=j;
    }
    j=0;
    for(int i=1;i<=la;++i)
    {
        while(j>0 && b[j+1]!=a[i]) j=next_[j];
        if(b[j+1]==a[i]) j++;
        if(j==lb)
        {
            cout<<i-lb+1<<'\n';
            j=next_[j];
        }
    }
    for(int i=1;i<=lb;++i)
        cout<<next_[i]<<" ";
}

动物园

有趣的题

预处理串的长度然后 num 数组按题意模拟即可（不是

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7+50;
const int p=1e9+7;
int la,lb,next_[N],n;
int sum[N];
char a[N];
signed main()
{
    cin>>n;
    while(n--)
    {
        memset(next_,0,sizeof(next_));
        memset(sum,0,sizeof(sum));
        cin>>a+1;
        la=strlen(a+1);
        int ans=1;
        sum[1]=1,next_[1]=0;
        for(int i=2,j=0;i<=la;++i)
        {
            while(j && a[i]!=a[j+1])
                j=next_[j];
            if(a[j+1]==a[i]) j++;
            next_[i]=j;
            sum[i]=sum[j]+1;
        }
        for(int i=1,j=0;i<=la;++i)
        {
            while(j>0 && a[j+1]!=a[i]) j=next_[j];
            if(a[j+1]==a[i]) j++;
            while(j>i/2) j=next_[j];
            ans=(ans*(sum[j]+1))%p;
        }
        cout<<ans<<'\n';
    }
}

Censoring S

KMP删除操作，栈模拟，如果匹配到了子串就出栈即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7+50;
const int p=1e9+7;
int la,lb,next_[N],n;
int pos[N],top,sta[N];
char a[N],b[N];
signed main()
{
    cin>>a+1>>b+1;
    int la=strlen(a+1),lb=strlen(b+1);
    for(int i=2,j=0;i<=lb;++i)
    {
        while(j && b[i]!=b[j+1])
            j=next_[j];
        if(b[j+1]==b[i]) j++;
        next_[i]=j;
    }
    for(int i=1,j=0;i<=la;++i)
    {
        while(j && a[i]!=b[j+1]) j=next_[j];
        if(b[j+1]==a[i]) j++;
        pos[i]=j;
        sta[++top]=i;
        if(j==lb) top-=lb,j=pos[sta[top]];
    }
    for(int i=1;i<=top;++i)
        cout<<a[sta[i]];
}

【XR-3】系统设计

写的最久的题，挑了一下午发现线段树写假了