• 周二. 7 月 16th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

字符串算法汇总

admin

11 月 28, 2021

字符串算法都好难啊……

1. 字符串哈希

#define int long long
int n,cnt,finalans;
int mod1=1e9+7,base=107,mod2=1e9+9;
struct node{int x,y;}a[10010];
bool cmp(node a,node b)
{
    if(a.x!=b.x)return a.x<b.x;
    return a.y<b.y;
}
int hash1(string s)
{
    int ans=0,l=s.length();
    for(int i=0;i<l;i++)ans=(ans*base%mod1+(s[i]-'0'+1))%mod1;
    return ans;
}
int hash2(string s)
{
    int ans=0,l=s.length();
    for(int i=0;i<l;i++)ans=(ans*base%mod2+(s[i]-'0'+1))%mod2;
    return ans;
}
signed main()
{
    //...
    for(int i=1;i<=n;i++)
    {
        string s;cin >> s;
        a[++cnt].x=hash1(s);
        a[cnt].y=hash2(s);
    }
    finalans=n;
    sort(a,a+n+1,cmp);
    for(int i=1;i<n;i++)
        if(a[i].x==a[i+1].x||a[i].y==a[i+1].y)
            finalans--;
    cout << finalans;
    return 0;
}

2. KMP

3. manacher

4. Trie树

5. 最小表示法

6. Z函数(exKMP)

7. AC自动机

8. 子序列自动机

9. 后缀数组

10. 后缀自动机

11. 回文自动机

发表回复