寒假算法训练（二）字符串算法

发表于 更新于 分类于 ，

#Algo0201.# 【模板】字符串哈希

题目描述

题目需要求出给定字符串中是否有重复的，利用桶存储字符串的Hash，并判断该Hash是否存在。

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
40
41
42
char s[2001];
int n,ans;
const int N=100005;
int a[43961944];

struct Hash
{
    const int Mod1=43961944,u1=131;
    int h1[N],b1[N];
    void build(char *s)
    {
        b1[0]=1;
        for (int i=1;i<=strlen(s+1);i++)
        {
            b1[i]=b1[i-1]*u1%Mod1;
            h1[i]=(h1[i-1]*u1+s[i]-48)%Mod1;
        }
    }

    int getHash(int l,int r)
    {
        return (h1[r]-h1[l-1]*b1[r-l+1]%Mod1+Mod1)%Mod1;
    }
}Hash;

int main()
{
    CI n;
    F(i,1,n)
    {
        CI (s+1);
        Hash.build(s);
        int h=Hash.getHash(1,strlen(s+1));
        if (a[h]==0) 
        {
            a[h]=1;
            ans++;
        }
    }
    CO ans L;  
    return 0;
}

#Algo0202.# 【模板】KMP字符串匹配

题目描述

本题利用KMP算法，输出模式串匹配的位置，并在结尾打印next数组。

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
int n,m,nxt[1000006];
char a[1000006],b[1000006];
int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI (a+1)>>(b+1);
    n=strlen(a+1);
    m=strlen(b+1);
    nxt[1]=0;
    int j=0;
    for (int i=2;i<=m;i++)
    {
        while (b[i]!=b[j+1]&&j>0)
            j=nxt[j];
        if (b[i]==b[j+1])
        {
            j++;
            nxt[i]=j;
        }
    }

    j=0;
    for (int i=0;i<n;i++)
    {
        while (a[i+1]!=b[j+1]&&j>0)
            j=nxt[j];
        if (a[i+1]==b[j+1]) j++;
        if (j==m) cout<<i+1-m+1<<endl;
    }
    for (int i=1;i<=m;i++)
        cout<<nxt[i]<<" ";
    cout<<endl;
    return 0;
}

#Algo0203.# Censoring S

题目描述

本题利用KMP查找模式串的同时，用一个栈来记录答案，并用top指针指向栈顶，同时用一个栈f来记录字符串每位的j指针位置。当匹配到模式串后，top数组后移模式串的位数，同时将j指针调整到f栈栈顶记录的位置处。这样就可以在匹配到一个字符串后，将j指针还原到上一次匹配的情况。

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
int n,m,nxt[1000006],f[1000006];
char a[1000006],b[1000006],c[1000006];

int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI (a+1)>>(b+1);
    n=strlen(a+1);
    m=strlen(b+1);
    nxt[1]=0;
    int j=0;
    for (int i=2;i<=m;i++)
    {
        while (b[i]!=b[j+1]&&j>0)
            j=nxt[j];
        if (b[i]==b[j+1])
        {
            j++;
            nxt[i]=j;
        }
    }

    int top=0;
    for (int i=0;i<n;i++)
    {
        c[++top]=a[i+1];
        // cout<<top<<c[top]<<endl;
        while ((a[i+1]!=b[j+1])&&j>0)
            j=nxt[j];

        if (a[i+1]==b[j+1]) j++;
        f[top]=j;
        if (j==m) top-=m,j=f[top];
    }
    c[++top]='\0';
    cout<<(c+1)<<endl;
    return 0;
}

#Algo0204.# 无线传输

题目描述

字符串有一个循环节构成，求循环节的最小长度。输出这个字符串的next数组，不难发现，当循环节开始循环时，next值从1逐个增加，并在末尾处，next值表示该数组循环了多少位。将字符串总长度减去最后一位的next就能得到循环节的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int n,m,nxt[1000006],ans=0;
char b[1000006];
int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI m;
    CI (b+1);
    m=strlen(b+1);
    nxt[1]=0;
    int j=0;
    for (int i=2;i<=m;i++)
    {
        while (b[i]!=b[j+1]&&j>0)
            j=nxt[j];
        if (b[i]==b[j+1])
        {
            j++;
            nxt[i]=j;
        }
    }

    cout<<m-nxt[m]<<endl;
    return 0;
}