2019牛客国庆集训派对day1 C Distinct Substrings

亦凉 2023-06-02 15:56 15阅读 0赞

## 题意：[https://ac.nowcoder.com/acm/contest/1099/C][https_ac.nowcoder.com_acm_contest_1099_C]。 ##

## 分析：大致题意是说向字符串末尾添加任意字符所增加的不同子串个数。容易知道，新增的子串一定是后缀，如果新增字符没有出现过，那么贡献n+1，n为字符串的长度，如果出现过了，容易发现如果这个字符的前一个位置的的前缀的后缀和原串的后缀部分相同，那么肯定有重复的，重复的个数就是两个前缀的最长公共后缀长度+1（因为包括当前字符，所以+1），直接做不好怎么求，可以将字符串反转，转化为两个的后缀的最长公共前缀，可以用扩展kmp或者（Z算法）来求公共前缀z\[i\]（z\[i\]表示倒过来的字符串中以i为起点的后缀子串与倒过来的字符串的最长公共前缀）   求的z数组之后就可以计算best数组（best\[i\]表示在原字符串中添加i之后会得到比原字符串新加的重复子串个数）   S\[\]=(1,2,1,3,1,2,1)   倒过来 1 2 1 3 1 2 1   z\[\]=(0,0,1,0,3,0,1)   Best\[s\[i\]\]=max(best\[s\[i\]\],1+z\[i+1\]) ：因为在第i+1个数字有z\[i+1\]个公共前缀，所以添加i的话，就会多出z\[i+1\]+1个重复的子串（倒转之后前变后）。参考[https://blog.csdn.net/qq\_43202683/article/details/100170570][https_blog.csdn.net_qq_43202683_article_details_100170570]。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int N = 1e6+5;
    const ll mod = 1e9+7;
    int n,m,z[N];
    vector<int> s;
    
    void get_z()
    {
        int l=0,r=0;
        for (int i=1;i<n;i++)
        {
            if (i>r)
            {
                l=i,r=i;
                while (r<n && s[r-l]==s[r]) r++;
                z[i]=r-l,r--;
            }
            else
            {
                int k=i-l;
                if (z[k]<r-i+1) z[i]=z[k];
                else
                {
                    l=i;
                    while (r<n && s[r-l]==s[r]) r++;
                    z[i]=r-l,r--;
                }
            }
        }
    }
    
    int main(){
        while(~scanf("%d%d",&n,&m)) {
            s.resize(n);
            for(int i=0;i<n;i++) scanf("%d",&s[i]);
            reverse(s.begin(),s.end());
            for(int i=0;i<=n;i++) z[i] = 0;
            get_z();
            vector<int> best(m+1);
            for(int i=0;i<n;i++)
                best[s[i]] = max(best[s[i]], 1 + z[i+1]);
            ll ans = 0, th = 3;
            for(int i=1;i<=m;i++) {
                ans ^= th * (n + 1 - best[i]) % mod;
                (th *= 3) %= mod;
            }
            printf("%lld\n",ans);
        }
    	return 0;
    }

[https_ac.nowcoder.com_acm_contest_1099_C]: https://ac.nowcoder.com/acm/contest/1099/C
[https_blog.csdn.net_qq_43202683_article_details_100170570]: https://blog.csdn.net/qq_43202683/article/details/100170570