学习笔记-字符串

· · 算法·理论

字符串

算是一种数据结构，但知识点和用途较广泛，所以单开一节。

字符串哈希

通常使用字符串哈希实现两字符串之间快速比较。

进制哈希（\text{BKDR Hash}）

将字符串当作 n 进制数，然后进行计算（自然溢出）。

模板代码实现。

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
constexpr int X=1e4+5;
constexpr ull st=13131ull;

ull N,res,H[X];
string s[X];

ull make_hash(string &s)
{
    ull h=0;
    for(auto c:s)
        h*=st, h+=c;
    return h;
}

int main()
{
    cin>>N;
    for(int i=1;i<=N;i++){
        cin>>s[i];
        H[i]=make_hash(s[i]);
    }
    sort(H+1,H+N+1);
    for(int i=1;i<=N;i++)
        if(H[i]!=H[i-1]) res++;
    cout<<res;
    return 0;
}

STL 实现

利用 unordered_map 或 unordered_set 可以方便地实现字符串哈希。

如果怕被卡，可以使用 map 或者 set，复杂度要劣一些。

#include<bits/stdc++.h>
using namespace std;
constexpr int X=1e4+5;

int N;
string s[X];
unordered_set<string> S;

int main()
{
    cin>>N;
    for(int i=1;i<=N;i++){
        cin>>s[i];
        S.insert(s[i]);
    }
    cout<<S.size();
    return 0;
}

大数据下可能会 MLE，也可以手压成 Hash 值然后装入 STL 容器。

字典树（Trie）

相当实用的数据结构，可以在串长复杂度内求解前缀匹配问题。可用于 AC 自动机的失配回溯。其变种 0-1 Trie 广泛用于求解异或问题。缺点是空间复杂度较劣。

核心是插入和查找。

插入时顺着节点编号向下记录，若遇到空节点就新增节点，查找类似。

模板代码如下：

#include<bits/stdc++.h>
using namespace std;
constexpr int X=3e6+5;

int T,N,q;
string s;

struct Trie{
    struct Node{
        int p[128];
        int cnt;
        void clear()
        {
            for(int i=1;i<127;i++) p[i]=0; cnt=0;
        } 
    }t[X];
    int lst;
    void clear()
    {
        for(int i=0;i<=lst;i++) t[i].clear(); lst=0;
    }
    void insert(string &s)
    {
        int pos=0;
        for(auto c:s){
            if(!t[pos].p[c]) t[pos].p[c]=++lst;
            pos=t[pos].p[c];
            t[pos].cnt++;
        }
    }
    int query(string &s)
    {
        int pos=0;
        for(auto c:s){
            if(!t[pos].p[c]) return 0;
            pos=t[pos].p[c];
        }
        return t[pos].cnt;
    }
}Tr;

void solve()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0); 
    Tr.clear();
    cin>>N>>q;
    while(N--){
        cin>>s;
        Tr.insert(s);
    }
    while(q--){
        cin>>s;
        cout<<Tr.query(s)<<'\n';
    }
}

int main()
{
    cin>>T;
    while(T--) solve();
}

\text{KMP}

非常精妙，简洁，优秀的一个算法，用于在 O(n+m) 复杂度内求解字符串单模匹配问题，其使用 fail 数组维护模式串的最长公共前后缀，以在失配后避免重新匹配。

代码如下：

#include<bits/stdc++.h>
using namespace std;
constexpr int X=1e6+5;

int N,M,fail[X];
string s,p;

void print(int i)
{
    cout<<i-M+2<<'\n';
}

void get_fail()
{
    fail[0]=0, fail[1]=0;
    for(int i=1;i<M;i++){
        int j=fail[i];
        while(j&&p[i]!=p[j]) j=fail[j];
        if(p[i]==p[j]) fail[i+1]=j+1;
        else fail[i+1]=0;
    }
}

void KMP()
{
    int j=0;
    for(int i=0;i<N;i++){
        while(j&&s[i]!=p[j]) j=fail[j];
        if(s[i]==p[j]) j++;
        if(j==M){
            print(i);
            j=fail[j];
        } 
    }
}

int main()
{
    cin>>s>>p;
    N=s.size(), M=p.size();
    get_fail(); KMP(); 
    for(int i=1;i<=M;i++) cout<<fail[i]<<' ';
}

\text{Manacher}

一个能在 O(n) 复杂度内求解字符串中以各个字符为中心的最长回文串的半径长度。其核心是利用 ”回文在回文中的镜像也是回文“ 来避免暴力匹配。

下面是模板代码：

#include<bits/stdc++.h>
using namespace std;
constexpr int X=2.3e7;

int N,P[X],res;
string a,s;

void change()
{
    N=a.size();
    s.append("$#");
    for(int i=0;i<N;i++){
        s.push_back(a[i]);
        s.push_back('#');
    }
    s.push_back('&');
    N=s.size();
}

void Manacher()
{
    int R=0,C=0;
    for(int i=1;i<N;i++){
        P[i]=(i<R)? min(P[(C<<1)-i],P[C]+C-i):1;
        while(s[i+P[i]]==s[i-P[i]]) P[i]++;
        if(P[i]+i>R) R=P[i]+i,C=i;
        res=max(res,P[i]-1);
    }   
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>a;
    change();
    Manacher();
    cout<<res; 
}