0721 学习记录

今天集训休息，自己看了看代码源的视频补知识点

kmp 相关

子串查询

输入两个字符串 $s$, $p$，查询 $p$ 是否在 $s$ 中出现，若出现输出出现位置，否则输出 $-1$

简化版

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


#include <bits/stdc++.h>
using namespace std;

string s,p;
int nxt[100001],f[100001],n,m;

void kmp(){
    n=s.size();
    m=p.size();
    int j=0;
    nxt[0]=0;
    p=p+"#"+s;
    for(int i=1;i<m+n+1;i++){
        while(j&&p[i]!=p[j])
            j=nxt[j-1];
        if(p[i]==p[j])
            j++;
        nxt[i]=j;
    }
    for(int i=m+1;i<n+m+1;i++){
        if(nxt[i]==m)cout<<i-2*m+1<<endl;
    }
}

int main(){
    cin>>s>>p;
    kmp();
    return 0;
}

常规版

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


#include <bits/stdc++.h>
using namespace std;

string s,p;
int nxt[100001],f[100001],n,m;

void kmp(){
    n=s.size();
    m=p.size();
    int j=0;
    nxt[0]=0;
    for(int i=1;i<m;i++){
        while(j&&p[i]!=p[j])
            j=nxt[j-1];
        if(p[i]==p[j])
            j++;
        nxt[i]=j;
    }
    j=0;
    for(int i=0;i<n;i++){
        while(j==m||(j&&s[i]!=p[j]))
            j=nxt[j-1];
        if(s[i]==p[j])
            j++;
        f[i]=j;
    }
    for(int i=0;i<n;i++){
        if(f[i]==m)cout<<i<<endl;
    }
}

int main(){
    cin>>s>>p;
    kmp();
    return 0;
}

寻找最小循环子串

字符串 $s$ 是由某个子串重复连接而成的，寻找构成 $s$ 的最小子串的长度

答案其实就是 $n - \text{nxt}[n]$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


#include <bits/stdc++.h>
using namespace std;

string s,p;
int nxt[100001],n,m;

void kmp(){
    m=p.size();
    int j=0;
    nxt[0]=0;
    p=p;
    for(int i=1;i<m;i++){
        while(j&&p[i]!=p[j])
            j=nxt[j-1];
        if(p[i]==p[j])
            j++;
        nxt[i]=j;
    }
    cout<<m-nxt[m-1]<<endl;
}

int main(){
    cin>>p;
    kmp();
    return 0;
}

Secret word

给出字符串 $s$，寻找最长字符串 $p$，$p$ 满足（是 $s$ 的子串，翻转后是 $s$ 的前缀）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


#include <bits/stdc++.h>
using namespace std;

string s;
int nxt[200001],n;

void kmp(){
    n=s.size();
    int j=0;
    nxt[0]=0;
    string t=s;
    reverse(t.begin(),t.end());
    s=s+"#"+t;
    for(int i=1;i<n*2+1;i++){
        while(j&&s[i]!=s[j])
            j=nxt[j-1];
        if(s[i]==s[j])
            j++;
        nxt[i]=j;
    }
    int ans=-1;
    for(int i=n;i<2*n+1;i++){
        ans=max(ans,nxt[i]);
    }
    for(int i=ans-1;i>=0;i--)cout<<s[i];
}

int main(){
    cin>>s;
    kmp();
    return 0;
}

exkmp

洛谷 P5410

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


#include <bits/stdc++.h>
using namespace std;
const int N = 2e7+10;
typedef long long ll;

string s,p;
ll z[N*2],n,m;

void exkmp(string s,string p){
    n=s.size();
    m=p.size();
    p=p+"#"+s;
    ll L=0,R=-1;
    z[0]=m;
    for(int i=1;i<n+m+1;i++){
        if(i>R)
            z[i]=0;
        else{
            ll k=i-L;
            z[i]=min(z[k],R-i);
        }
        while(i+z[i]<n+m+1&&p[z[i]]==p[i+z[i]])
            ++z[i];
        if(i+z[i]-1>R)
            L=i,R=i+z[i]-1;
    }
    ll ans=0;
    for(int i=0;i<m;i++)ans^=(1LL*(i+1)*(z[i]+1));
    cout<<ans<<"\n";
    ans=0;
    for(int i=0;i<n;i++)ans^=(1LL*(i+1)*(z[i+m+1]+1));
    cout<<ans<<"\n";
}

int main(){
    cin>>s>>p;
    exkmp(s,p);
    return 0;
}