2.2.2子串的個(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è)做法比直接累加要好些。