Distinct Substrings（扩展KMP）

Distinct Substrings

写完这题发现自己曾经的扩展KMP板子（ $Z$Z函数）太laji了！现在的板子简洁又漂亮，并且这题很妙！

题意：

给定一个长为 $n$n的数字串，问在尾部独立的添加 $1$1~ $m$m这些数字分别会使原串增加多少本质不同的子串

思路：

1. 看到本质不同，首先想到了后缀自动机，每次在结尾插入元素后只需要知道插入元素的父节点是谁，然后利用 $len\left[np\right]-len\left[fa\right[np\left]\right]$len[np]−len[fa[np]]就可以知道增加了多少新的本质不同的子串
2. 但就本题而言，有如下三点会否定这个做法：
   1. 空间 $32M$32M，而后缀自动机要开很多的 $1e6$1e6的数组
   2. 数组元素是数字，而不是字符，因此假设用 $map$map存边，空间会爆炸！
   3. 多组数据+ $O\left(nlogn\right)$O(nlogn)+大常数在两秒内显然是跑不出来的
3. 否定后缀自动机后，我们仍然可以利用这个求新增子串的思想；在后缀自动机中，思考一个节点的 $father$father节点是什么？答案是与当前节点 $endpos$endpos不同的最长的后缀，因此我们如果能够在不建立后缀自动机的情况下找到这个最长的后缀，那不就好了？
4. 而正好， $Z$Z $algorithm$algorithm刚好有一种经典的做法，考虑将原字符串翻转，就可以将求最长的后缀变成了求最长的前缀。并且要考虑分别添加 $m$m个不同数字的情况下的子串增量，我们可以 $O\left(n\right)$O(n)的计算贡献，见如下式子：
   $best\left[s\right[i\left]\right]=max\left(best\right[s\left[i\right]],1+z[i+1\left]\right)$best[s[i]]=max(best[s[i]],1+z[i+1])
   其中 $best\left[p\right]$best[p]表示在翻转后的串的前面增加 $p$p这个字符会有多少重复的子串出现，则 $n+1-best\left[p\right]$n+1−best[p]就表示新增的本质不同的子串数量。这个 $max$max旨在寻找最长的前缀
5. 最后，此问题可以在 $O(T\ast n)$O(T∗n)的复杂度下解决，并且空间复杂度也完全 $OK$OK（不过这题数据好像有些问题，导致暴力 $（O\left(n^2\right)）$（O(n2)）求 $z$z数组也能过。。。）

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 1e6+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-7;

int n, m;
int s[maxn], z[maxn], best[maxn];

int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    while(cin>>n>>m) {
        for(int i=1; i<=n; ++i) scanf("%d", &s[i]);
        reverse(s+1,s+1+n);
        for(int i=2, j=1; i<=n; ++i) {
            if(i<j+z[j]) z[i]=min(j+z[j]-i,z[i-j+1]);
            while(i+z[i]<=n&&s[i+z[i]]==s[z[i]+1]) z[i]++;
            if(i+z[i]>j+z[j]) j=i;
        }
        for(int i=1; i<=n; ++i) best[s[i]]=max(best[s[i]],1+z[i+1]);
        ll ans=0, three=1;
        for(int i=1; i<=m; ++i) {
            three=three*3%mod;
            ans^=three*(n+1-best[i])%mod;
        }
        cout<<ans<<endl;
        for(int i=1; i<=max(n,m); ++i) best[i]=z[i]=0;
    }
}