２．２．２子串的個(gè)數(shù)
例5：不相同的子串的個(gè)數(shù)（spoj694,spoj705）
給定一個(gè)字符串，求不相同的子串的個(gè)數(shù)。
算法分析：
每個(gè)子串一定是某個(gè)后綴的前綴，那么原問題等價(jià)于求所有后綴之間的不相
同的前綴的個(gè)數(shù)。如果所有的后綴按照suffix(sa[1]), suffix(sa[2]),
suffix(sa[3]), …… ,suffix(sa[n])的順序計(jì)算，
不難發(fā)現(xiàn)，對于每一次新加
進(jìn)來的后綴suffix(sa[k]),它將產(chǎn)生n-sa[k]+1 個(gè)新的前綴。但是其中有
height[k]個(gè)是和前面的字符串的前綴是相同的。所以suffix(sa[k])將“貢獻(xiàn)”
出n-sa[k]+1- height[k]個(gè)不同的子串。累加后便是原問題的答案。這個(gè)做法
的時(shí)間復(fù)雜度為O(n)。
看的時(shí)候怎么都沒看懂為什么要加一，從他論文里給出的模板來看，sa[i]的取值應(yīng)該從0 to n-1,帶了一下1111這個(gè)數(shù)據(jù)，顯然加一是錯(cuò)誤的。后來用模板做了下spoj 694，加1WA,反之AC，證明了我的想法，看來羅同學(xué)的表達(dá)有些前后不一致了。
另外，羅同學(xué)在給出的標(biāo)程中并沒有使用他給出的解法，而是轉(zhuǎn)了個(gè)彎，等差數(shù)列求和算出所有后綴長度的總和，然后在減去height[i](i from 1 to n),
這個(gè)做法比直接累加要好些。