試題 H: 子串分值和
時(shí)光限制: 1.0s 內(nèi)存限制: 256.0MB 本題總分：20 分
【問題描述】
對于一個(gè)字符串 S，我們定義 S 的分值 f(S ) 為 S 中出現(xiàn)的不合的字符個(gè)
數(shù)。例如 f(”aba”) = 2，f(”abc”) = 3, f(”aaa”) = 1。
如今給定一個(gè)字符串 S [0…n 1]（長度為 n），請你計(jì)算對于所有 S 的非空
子串 S [i… j](0 ≤ i ≤ j < n)，f(S [i… j]) 的和是若干。

【輸入格局】

輸入一行包含一個(gè)由小寫字母構(gòu)成的字符串 S。

【輸出格局】

輸出一個(gè)整數(shù)表示謎底。

【樣例輸入】

ababc

【樣例輸出】

28

【樣例解釋】

子串 f值 a 1
ab 2
aba 2
abab 2
ababc 3
b 1
ba 2
bab 2
babc 3
a 1
ab 2
abc 3
b 1
bc 2
c 1

【評(píng)測用例范圍與商定】
對于 20% 的評(píng)測用例，1 ≤ n ≤ 10；
對于 40% 的評(píng)測用例，1 ≤ n ≤ 100；
對于 50% 的評(píng)測用例，1 ≤ n ≤ 1000；
對于 60% 的評(píng)測用例，1 ≤ n ≤ 10000；
對于所有評(píng)測用例，1 ≤ n ≤ 100000。

思路:
以ababc為例
定義一個(gè)數(shù)組存放每個(gè)字母出現(xiàn)的次數(shù),len表示不是0的字母的個(gè)數(shù)
第一次for輪回大年夜左往右
那么每拜訪一個(gè)字符,次數(shù)++

當(dāng)前串狀況alen = 1 ,a = 1ablen = 2 ,a = 1, b = 1abalen = 2 , a = 2, b = 1abablen = 2 ,a = 2, b = 2ababclen = 3 , a = 2, b = 2, c = 1

接下來,for輪回大年夜左到右,然則刪除字符串最左邊的值

當(dāng)前串狀況babca-- , len = 3 a = 1, b = 2, c = 1abcb-- , len = 3 a = 1, b = 1, c = 1bca-- , len = 2 a = 0, b = 1, c = 1cb-- ,len = 1 a = 0, b = 0, c = 1

由此可見,兩次輪回下去只用O(2N)的時(shí)光求出來大年夜量的須要累加的字符串

然則ababc中心的子串bab以及以此為基本的字串都沒有被推敲到,所以此時(shí),只須要在外層新加一財(cái)揭捉環(huán),l=0,r = str.length() ,只要l<r,就輪回,然后l++,r- -,最后就能推敲到所有的情況
代碼:

因?yàn)榻裉靹偪纪険?dān)心被查重體系誤判,故放下圖片,不放源碼,同理,不包管代碼精確:


彌補(bǔ)一下,我測驗(yàn)測驗(yàn)生成了一個(gè)長度為10的4 次方的數(shù)據(jù)運(yùn)行代碼,可以1s內(nèi)出現(xiàn)謎底,然則換成10的5次方的數(shù)據(jù)就不可了,而正常的暴力解軌則對于10的3次方就是極限,10的四次方長度的字符串則運(yùn)行不出結(jié)不雅.