【問題解】2019牛客国慶節合宿パーティーday 1 C Distinct Substrings Z関数

テーマ出所:2019湖南省省省試合C題
現在、長さn(1 e 6)、文字セットm(1 e 6)の文字列Sがあり、1文字cに対してh(c)=S cの異なるサブストリング個数−Sの異なるサブストリング個数h(c)=Scの異なるサブストリング個数−Sの異なるサブストリング個数h(c)=Scの異なるサブストリング個数h(c)=Scの異なるサブストリング個数−Sの異なるサブストリング個数を定義し、すなわち、末尾にcを追加した後にいくつかの異なるサブストリングを追加し、求めるΣ c = 1 m h ( c )\Sigma_{c=1}^mh(c) Σc=1m​h(c). 複数のデータのグループ、Σ n , Σ m < = 5 e 5\Sigma n,\Sigma m<=5e5 Σn,Σm<=5 e 5、空間制限32 M、時間制限1 s
1.接尾辞自動機解法
文字セットが大きいため、mapを使用して転送を保存するため、Sに接尾辞オートマトンを確立します.接尾辞オートマチックでは、各ノードに対応する異なるサブ列の個数はlen(u)−len(link(u))に等しい.
各文字cに複数の異なるサブ列が追加されるかを列挙します.最後に1つの文字を追加すると、curとcloneの2つのノードが作成されることに注意してください.
一方、link(clone)=元のlink(q)であり、新しいlink(q)=cloneであるため、cloneノードは新しい文字列を格納しません.
curのlinkは0かqか、挿入規則に従って探せば答えが得られる.

	inline int try_extend(int c) const
	{
		int p = lst;
		while(!ch[p].count(c) && p)
			p = link[p];
		if(ch[p].count(c))
		{
			return len[lst] - len[p];
		}
		else
		{
			return len[lst] + 1;
		}
	}

この方法は失敗し、空間を爆発させた.
2.接尾辞配列解法
まずSの接尾辞配列を求め,本質的に異なるサブストリング個数がn∗(n+1)/2−に等しいことに注意する.Σ H e i g h t n * (n+1)/2 -\Sigma Height n∗(n+1)/2−ΣHeight.
末尾に新たに1文字cを挿入すると、新たに増加した異なるサブ列の個数は、n+1−h e i g h tの増分n+1−heightの増分n+1−heightの増分に等しい.
Sにcがない場合、height増分は0である.cがある場合、少なくとも1は、「c」接尾辞が新しく追加されたためです.
残りのheightはどれが増加しますか?注意height[i]はsa[i]とsa[i−1]のlcpを表すため、h e i g h t[i]=l e n(s a[i−1])height[i]=len(sa[i−1])height[i]=len(sa[i−1])であり、S[s a[i]+h e i g h t[i]=c S[sa[i]+height[i]=c S[sa[i]+height[i]=cの場合、Sの末尾に1文字cが追加され、heightが1つ加算される.ここでlen(sa[i−1])は、sa[i−1]番目の接尾辞の長さを表し、値はn−sa[i−1]である.
cnt[c]が文字がcの場合heightの増分であることを覚え、height配列を1回遍歴するとすべての答えが見つかります.

for(int i=2; i<=n; ++i)
	if(height[i] == n-sa[i-1])
		++cnt[str[sa[i]+height[i]]];

この方法は失敗し,倍増法はSAタイムアウトを求め,DC 3はSA爆空間を求める.
3.Z関数解法
上記の2つの方法の原理をよく考えると、ScはSに比べてn+1のサブストリングを新たに増加し、それぞれ[1...n+1],[2...n+1],...,[n+1...n+1]である.これらのサブストリングはSに既に出現していれば,これ以上カウントされない.注意[k...n+1]が時代遅れになると、[k+1...n+1],[k+2,n+1],...はその接尾辞として必ず現れる.
したがって、Scの最長接尾辞がSに現れるように見つかれば、h(c)=n+1−接尾辞長h(c)=n+1−接尾辞長h(c)=n+1−接尾辞長h(c)=n+1−接尾辞長である.この接尾辞の終わりはcに違いない.
ここで、Sの各真接頭辞s[1…i]について、Sとの最長共通接尾辞lcsを求めると、h(s[i+1])=m i n(h(s[i+1]),(n+1)−(lc s+1])h(s[i+1])=min(h(s[i+1]),(n+1)−(lcs+1))h(s[i+1])=min(h(s[i+1]),(n+1)−(lcs+1)).
Sを反転させてZ関数を用いると,すべてのlcsが得られる.

/* LittleFall : Hello! */
#include 
using namespace std; using ll = long long; inline int read();
const int M = 1000016, MOD = 1000000007;

int z[M]; //z  ，z[i]     s  i    s lcp，   0  。
void exkmp(int *s)
{
	for(int i=1,l=0,r=0; s[i]; ++i)
	{
		z[i] = i>r ? 0 : min(r-i+1, z[i-l]);
		while(s[i+z[i]] && s[z[i]]==s[i+z[i]]) ++z[i];
		if(i + z[i] - 1 > r) l=i, r=i+z[i]-1;
	}
}
int str[M], h[M];
ll p3[M];
int main(void)
{
	#ifdef _LITTLEFALL_
	freopen("in.txt","r",stdin);
    #endif

	p3[0] = 1;
	for(int i=1; i<M; ++i)
		p3[i] = p3[i-1] * 3 % MOD;
	int n=0, m=0;
	while(~scanf("%d%d",&n,&m))
	{
		for(int i=1; i<=m; ++i)
			h[i] = n+1;
		for(int i=n-1; i>=0; --i)
		{
			str[i] = read();
			h[str[i]] = n;
		}
		str[n]=0;

		exkmp(str);
		for(int i=1; i<n; ++i)
			h[str[i-1]] = min(h[str[i-1]], n-z[i]);

		ll ans = 0;
		for(int i=1; i<=m; ++i)
			ans ^= h[i]*p3[i] % MOD;
		printf("%lld
",ans );
	}

    return 0;
}


inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

まとめ:

多く問題の本質を考えて、あまり技術に依存しないでください.

は表面的にはSAMやSAで過ごせますが、時間空間がきつい場合はkmpを拡張する必要があるかもしれません.