洛谷字符串题单

P3375 【模板】KMP

https://www.luogu.com.cn/problem/P3375

#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
//#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
const int N=1e6+10;
int ne[N];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string a,b;
    cin>>a>>b;
    int n=a.size(),m=b.size();
    for(int i=1,j=0;i<m;i++)
    {
        while(j&&b[i]!=b[j])j=ne[j];
        if(b[i]==b[j])j++;
        ne[i+1]=j;
    }
    for(int i=0,j=0;i<n;i++)
    {
        while(j&&a[i]!=b[j])j=ne[j];
        if(a[i]==b[j])j++;
        if(j==m){
            cout<<i-m+1+1<<'\n';
            j=ne[j];
        }
    }
    for(int i=1;i<=m;i++)
    {
        cout<<ne[i]<<" \n"[i==m];
    }

    return 0;    
}

P4391 [BOI2009] Radio Transmission 无线传输

https://www.luogu.com.cn/problem/P4391

!(https://cdn.jsdelivr.net/gh/kkonglb/image/v1y85ooc.png)

感觉这个例子十分好理解，由题意得该字符串s1是由多个s2拼接而成的，而这可能是m个完成的s2拼接而成，也可能最后多出来一块，这个例子中最后多出来两个字母，那么前缀就是一个完整的s2+ca，后缀也是一个完整的s2+ca。答案就是n-ne[n]

#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
//#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
const int N=1e6+10;
int ne[N];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    string s;
    cin>>s;
    for(int i=1,j=0;i<n;i++)
    {
        while(j&&s[i]!=s[j])j=ne[j];
        if(s[i]==s[j])j++;
        ne[i+1]=j;
    }
    cout<<n-ne[n]<<'\n';

    return 0;    
}

P1481 魔族密码

https://www.luogu.com.cn/problem/P1481

#include <bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
// #define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
const int N = 2e5 + 10;
int nxt[N][26];
int cnt[N];
int dix;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int maxn = 0;
    for (int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;
        int p = 0;
        int jishu = 1;
        for (int i = 0; i < s.size(); i++)
        {
            int shu = s[i] - 'a';
            if (!nxt[p][shu])
                nxt[p][shu] = ++dix;
            p = nxt[p][shu];
            if (cnt[p])
                jishu += cnt[p];
        }
        cnt[p]++;
        maxn = max(maxn, jishu);
    }
    cout << maxn << '\n';

    return 0;
}

P2580 于是他错误的点名开始了

https://www.luogu.com.cn/problem/P2580

#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
const int N=5e5+10;
int nxt[N][26];
int cnt[N];
int dix;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        string s;
        cin>>s;
        int p=0;
        for(int i=0;i<s.size();i++)
        {
            int shu=s[i]-'a';
            if(!nxt[p][shu])nxt[p][shu]=++dix;
            p=nxt[p][shu];
        }
        cnt[p]++;
    }
    int m;
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        string s;
        cin>>s;
        int p=0;
        int ok=1;
        for(int i=0;i<s.size();i++)
        {
            int shu=s[i]-'a';
            if(!nxt[p][shu])
            {
                cout<<"WRONG\n";
                ok=0;
                break;
            }
            p=nxt[p][shu];
        }
        if(!ok)continue;
        if(cnt[p]==0)
        {
            cout<<"WRONG\n";
        }
        else if(cnt[p]==1)
        {
            cout<<"OK\n";
            cnt[p]++;
        }
        else 
        {
            cout<<"REPEAT\n";
        }
    }

    return 0;    
}

P4551 最长异或路径

https://www.luogu.com.cn/problem/P4551

#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
struct edge
{
    int v,w;
};
const int N=1e5+10;
int yh[N];
int nxt[10*N][2];
int dix;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<vector<edge>>adj(n+1);

    for(int i=2;i<=n;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }    
    auto dfs=[&](auto self,int u,int fa)->void{
        for(auto [v,w]:adj[u])
        {
            if(v==fa)continue;
            yh[v]=yh[u]^w;
            self(self,v,u);
        }
    };
    dfs(dfs,1,0);
    auto build=[&](int x){
        int p=0;
        for(int i=30;i>=0;i--)
        {
            bool ok=x&(1<<i);
            if(!nxt[p][ok])
            {
                nxt[p][ok]=++dix;
            }
            p=nxt[p][ok];
        }
    };
    for(int i=1;i<=n;i++)
    {
        build(yh[i]);
    }
    int maxn=0;
    auto query=[&](int x)->int{
        int p=0;
        int ans=0;
        for(int i=30;i>=0;i--)
        {
            bool ok=x&(1<<i);
            if(nxt[p][!ok]){
                p=nxt[p][!ok];
                ans+=(1<<i);
            }
            else p=nxt[p][ok];
        }
        return ans;
    };
    for(int i=1;i<=n;i++)
    {
        maxn=max(maxn,query(yh[i]));
    }
    cout<<maxn<<'\n';
    return 0;    
}