字符串

小咪咪 2021-10-23 06:53 513阅读 0赞

hash

[poj3461 Oulipo][]

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    #include<cstring>
    #define ull unsigned long long
    using namespace std; 
    ull power[1000005],sum[1000005];
    char s1[10005],s2[1000005];
    int main()
    {
        int t,b = 26;
        scanf("%d",&t);
        power[0] = 1;
        for(int i = 1;i <= 1000000;i++)
            power[i] = power[i - 1] * b;
        while(t--)
        {
            scanf("%s%s",s1 + 1,s2 + 1);
            int n = strlen(s1 + 1),m = strlen(s2 + 1);
            sum[0] = 0;
            for(int i = 1;i <= m;i++)
                sum[i] = sum[i - 1] * b + (ull)(s2[i] - 'A' + 1);
            ull s = 0;
            for(int i = 1;i <= n;i++)
                s = s * b +(ull)(s1[i] - 'A' + 1);
            int ans = 0;
            for(int i = 0;i <= m - n;i++)
                if(s == sum[i + n] - sum[i] * power[n])
                    ans++;
            printf("%d\n",ans);
        }
        return 0;
    }

kmp

[hdu2087 剪花布条][hdu2087]

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    #include<cstring>
    using namespace std;
    const int N = 1010;
    
    char a[N],b[N];
    int n,m;
    int nxt[N];
    void prepare()
    {
        nxt[1] = 0;
        int j = 0;
        for(int i = 1;i < m;i++)
        {
            while(j > 0 &&b[j + 1] != b[i + 1])
                j = nxt[j];
            if(b[j + 1] == b[i + 1])
                j++;
            nxt[i + 1] = j;
        }
    }
    int kmp()
    {
        int ans = 0,j = 0;
        for(int i = 0;i < n;i++)
        {
            while(j > 0 && b[j + 1] != a[i + 1])
                j = nxt[j];
            if(b[j + 1] == a[i + 1])
                j++;
            if(j == m)
            {
                j = 0;
                ans++;
            }
        }
        return ans;
    }
    int main()
    {
        while(~scanf("%s",a+1))
        {
            n = strlen(a + 1);
            if(a[1] == '#' && n == 1)
                break;
            scanf("%s",b+1);        
            m = strlen(b + 1);
            prepare();
            printf("%d\n",kmp());        
        }
        return 0;
    }

trie字典树

[poj3630 Phone List][]

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    const int N = 1e5 + 10;
    int n,tot;
    bool bo[N];
    int num[N][15];//num[u][c]以u为父节点，边权为c 
    char s[15];
    void clear()
    {
        memset(num,0,sizeof(num));
        memset(bo,0,sizeof(bo));
    }
    bool insert(char *s)
    {
        int len = strlen(s);
        int u = 1;
        bool flag = false;
        for(int i = 0;i < len;i++)
        {
            int c = s[i] - '0';
            if(!num[u][c])
                num[u][c] = ++tot;
            else if(i == len - 1)//新加入的字符串和以前的相同或者包毫爽以前的 
                flag = true;
            u = num[u][c];
            if(bo[u])
                flag = true;    
        }
        bo[u] = true;
        return flag;
    }
    int main()
    {
        int t;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d",&n);
            tot = 1;
            clear();
            bool ans = false;
            for(int i = 1;i <= n;i++)
            {
                scanf("%s",s);
                if(insert(s))
                    ans = true;
            }
            if(!ans)
                puts("YES");
            else
                puts("NO");
        }
        return 0;
    }

AC自动机

[洛谷3808 模板][3808]

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    #include<cstring>
    #include<queue>
    using namespace std;
    const int N = 1e6 + 10;
    int n;
    char s[N];
    queue<int> q;
    struct AC
    {
        int ch[N>>1][26],val[N>>1],nxt[N>>1],tot;
        void  insert(char *s)
        {
            int len = strlen(s);
            int now = 0;
            for(int i = 0;i < len;i++)
            {
                int v = s[i] - 'a';
                if(!ch[now][v])
                    ch[now][v] = ++tot;
                now = ch[now][v];
            }
            val[now]++;
        }
        void build()
        {
            for(int i = 0;i <= 25;i++)
                if(ch[0][i])
                {
                    nxt[ch[0][i]] = 0;
                    q.push(ch[0][i]);
                }
            while(!q.empty())
            {
                int u = q.front();
                q.pop();
                for(int i = 0;i < 26;i++)
                    if(ch[u][i])
                    {
                        nxt[ch[u][i]] = ch[nxt[u]][i];
                        q.push(ch[u][i]);
                    }
                    else
                        ch[u][i] = ch[nxt[u]][i]; 
            }
        }
        int query(char *s)
        {
            int len = strlen(s);
            int now = 0,ans = 0;
            for(int i = 0;i < len;i++)
            {
                now = ch[now][s[i] - 'a'];
                for(int t = now;t && ~val[t];t = nxt[t])
                {
                    ans += val[t];
                    val[t] = -1;
                }
            }
            return ans;
        }
    }ac;
    int main()
    {
        scanf("%d",&n);
        for(int i = 1;i <= n;i++)
        {
            scanf("%s",s);
            ac.insert(s);
        }
        ac.build();
        scanf("%s",s);
        int ans = ac.query(s);
        printf("%d",ans);
        return 0;
    }

转载于:https://www.cnblogs.com/darlingroot/p/11276121.html

[poj3461 Oulipo]: http://poj.org/problem?id=3461
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211023/69dce16908ec40e387f9e22f76d5c6ed.png
[hdu2087]: http://acm.hdu.edu.cn/showproblem.php?pid=2087
[poj3630 Phone List]: http://poj.org/problem?id=3630
[3808]: https://www.luogu.org/problem/P3808