字符串Hash + 二分

题目描述：

你需要从空字符串开始 构造 一个长度为 n 的字符串 s ，构造的过程为每次给当前字符串 前面 添加 一个 字符。构造过程中得到的所有字符串编号为 1 到 n ，其中长度为 i 的字符串编号为 si 。

    比方说，s = "abaca" ，s1 == "a" ，s2 == "ca" ，s3 == "aca" 依次类推。

si 的 得分 为 si 和 sn 的 最长公共前缀 的长度（注意 s == sn ）。

给你最终的字符串 s ，请你返回每一个 si 的 得分之和 。

Java代码：

 1 class Solution {
 2 
 3     int N = 100000 + 10;
 4 
 5     int P = 13131;
 6 
 7     long[] h = new long[N];
 8 
 9     long[] p = new long[N];
10 
11     public void setHAndP(char[] c, int n) {
12         p[0] = 1;
13         for (int i = 1; i <= n; i++) {
14             h[i] = h[i - 1] * P + (int)c[i - 1];
15             p[i] = p[i - 1] * P;
16         }
17     }
18 
19     public long sumScores(String s) {
20         char[] c = s.toCharArray();
21         int n = c.length;
22         setHAndP(c, n);
23         long res = 0;
24         for (int i = n; i >= 2; i--) {
25             int left = i;
26             int right = n;
27             while (left <= right) {
28                 int mid = (left + right) / 2;
29                 int len = mid - i + 1;
30                 int s1 = 1;
31                 int e1 = s1 + len - 1;
32                 int s2 = i;
33                 int e2 = mid;
34                 // 二分
35                 if (check(s1, e1, s2, e2)) {
36                     left = mid + 1;
37                 } else {
38                     right = mid - 1;
39                 }
40             }
41             res += (right - i + 1);
42         }
43         return res + n;
44     }
45     
46     // abcde
47     public boolean check(int s1, int e1, int s2, int e2) {
48         long r1 = h[e1] - (h[s1 - 1] * p[e1 - s1 + 1]);
49         long r2 = h[e2] - (h[s2 - 1] * p[e2 - s2 + 1]);
50         return r1 == r2;
51     }
52 }

力扣链接：

https://leetcode-cn.com/problems/sum-of-scores-of-built-strings/