class Solution {
public:
int distinctEchoSubstrings(string text) {
}
};
1316. 不同的循环子字符串
给你一个字符串 text ，请你返回满足下述条件的 不同 非空子字符串的数目：
a + a，其中 a 是某个字符串）。例如，abcabc 就是 abc 和它自身连接形成的。
示例 1：
输入：text = "abcabcabc" 输出：3 解释：3 个子字符串分别为 "abcabc"，"bcabca" 和 "cabcab" 。
示例 2：
输入：text = "leetcodeleetcode" 输出：2 解释：2 个子字符串为 "ee" 和 "leetcodeleetcode" 。
提示：
1 <= text.length <= 2000text 只包含小写英文字母。原站题解
golang 解法, 执行用时: 72 ms, 内存消耗: 2.3 MB, 提交时间: 2023-09-24 23:10:41
func distinctEchoSubstrings(text string) int {
// 连续的
res := make(map[string]bool)
for i := range text {
for j := i + 2; j <= len(text); j += 2 {
k := (i + j) / 2
if text[i:k] == text[k:j] {
res[text[i:k]] = true
}
}
}
return len(res)
}
python3 解法, 执行用时: 1940 ms, 内存消耗: 16.2 MB, 提交时间: 2023-09-24 23:10:15
class Solution:
def distinctEchoSubstrings(self, s: str) -> int:
MOD = 10**9+7
base = 31 # s仅包含小写字母，base可取31
'''字符编码函数'''
def encode(ch):
return ord(ch) - ord('a') + 1
n = len(s)
'''预处理出前缀字符串的哈希值 和 base进制的幂'''
prefix = [0] * (n+1) # prefix[i]: 字符串s[0:i]的哈希值
mul = [1] * (n+1) # mul[i]: base ** i
for i in range(1, n+1):
prefix[i] = ( prefix[i-1] * base + encode(s[i-1]) ) % MOD
mul[i] = mul[i-1] * base % MOD
ans = 0
visited = set()
for i in range(n-1):
for m in range(1, (n-i)//2+1): # 目标子串的长度m：[1, (n-i)//2]
'''左侧字符串: s[i, i+m-1], 右侧字符串: s[i+m, i+2m-1]'''
left = ( prefix[i+m] - prefix[i] * mul[m] % MOD + MOD ) % MOD
if left in visited: # 当前字符已被记录
continue
right = ( prefix[i+2*m] - prefix[i+m] * mul[m] % MOD + MOD ) % MOD
if left == right: # 左侧字符串 与 右侧字符串 相同
visited.add(left)
ans += 1
return ans
python3 解法, 执行用时: 2184 ms, 内存消耗: 16.8 MB, 提交时间: 2023-09-24 23:10:07
class Solution:
# kmp
def distinctEchoSubstrings(self, s: str) -> int:
def kmp(s):
ans = 0
n = len(s)
pi = [0] * n
j = 0
for i in range(1, n):
while j>0 and s[i] != s[j]: # 当前位置s[i]与s[j]不等
j = pi[j-1] # j指向之前位置，s[i]与s[j]继续比较
if s[i] == s[j]: # s[i]与s[j]相等，j+1，指向后一位
j += 1
pi[i] = j # pi[i]: s[0,..,i] 中相等的真前缀与真后缀的最长长度
# 以上代码为 KMP 模板
# 自此开始满足本题要求的字符数目统计：
m = i+1 # 当前前缀字符串的长度
if j !=0 and m % (m-j) == 0 and m // (m-j) % 2 == 0:
'''【m 需为 m-j 的偶数倍】'''
if s[:m//2] not in visited: # 当前前缀字符串的一半满足要求
visited.add(s[:m//2]) # 若不重复，则可计入
ans += 1
return ans
'''主程序'''
n = len(s)
visited = set()
ans = 0
for i in range(n-1):
ans += kmp(s[i:])
return ans
java 解法, 执行用时: 90 ms, 内存消耗: 43.2 MB, 提交时间: 2023-09-24 23:09:06
class Solution {
public int distinctEchoSubstrings(String text) {
int n = text.length(), ans = 0, base = 31, mod = (int) 1e9 + 7;
int[] pre = new int[n + 1];
int[] mul = new int[n + 1];
mul[0] = 1;
Set<Integer>[] set = new HashSet[n];
for (int i = 0; i < n; i++) {
set[i] = new HashSet<>();
pre[i + 1] = (int) (((long) pre[i] * base + (text.charAt(i) - 'a')) % mod);
mul[i + 1] = (int) (((long) mul[i] * base) % mod);
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
int l = j - i;
if (j + l <= n) {
int lh = getHash(pre, mul, i, j - 1, mod);
if (!set[l - 1].contains(lh) && lh == getHash(pre, mul, j, j + l - 1, mod)) {
ans++;
set[l - 1].add(lh);
}
}
}
}
return ans;
}
private int getHash(int[] pre, int[] mul, int l, int r, int mod) {
return (int) ((pre[r + 1] - (long) pre[l] * mul[r - l + 1]) % mod + mod) % mod;
}
}
cpp 解法, 执行用时: 160 ms, 内存消耗: 7.8 MB, 提交时间: 2023-09-24 23:08:38
using LL = long long;
class Solution {
private:
constexpr static int mod = (int)1e9 + 7;
public:
int gethash(const vector<int>& pre, const vector<int>& mul, int l, int r) {
return (pre[r + 1] - (LL)pre[l] * mul[r - l + 1] % mod + mod) % mod;
}
int distinctEchoSubstrings(string text) {
int n = text.size();
int base = 31;
vector<int> pre(n + 1), mul(n + 1);
pre[0] = 0;
mul[0] = 1;
for (int i = 1; i <= n; ++i) {
pre[i] = ((LL)pre[i - 1] * base + text[i - 1]) % mod;
mul[i] = (LL)mul[i - 1] * base % mod;
}
unordered_set<int> seen[n];
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int l = j - i;
if (j + l <= n) {
int hash_left = gethash(pre, mul, i, j - 1);
if (!seen[l - 1].count(hash_left) && hash_left == gethash(pre, mul, j, j + l - 1)) {
++ans;
seen[l - 1].insert(hash_left);
}
}
}
}
return ans;
}
};
python3 解法, 执行用时: 3564 ms, 内存消耗: 16.8 MB, 提交时间: 2023-09-24 23:07:59
class Solution:
# 枚举
def distinctEchoSubstrings2(self, text: str) -> int:
n = len(text)
seen = set()
ans = 0
for i in range(n):
for j in range(i + 1, n):
if j * 2 - i <= n and text[i:j] == text[j:j*2-i] and text[i:j] not in seen:
ans += 1
seen.add(text[i:j])
return ans
# 滚动哈希 + 前缀和
def distinctEchoSubstrings(self, text: str) -> int:
n = len(text)
mod, base = 10**9 + 7, 31
pre, mul = [0] * (n + 1), [1] + [0] * n
for i in range(1, n + 1):
pre[i] = (pre[i - 1] * base + ord(text[i - 1])) % mod
mul[i] = mul[i - 1] * base % mod
def get_hash(l, r):
return (pre[r + 1] - pre[l] * mul[r - l + 1] % mod + mod) % mod
seen = {x: set() for x in range(n)}
ans = 0
for i in range(n):
for j in range(i + 1, n):
l = j - i
if j + l <= n:
hash_left = get_hash(i, j - 1)
if hash_left not in seen[l - 1] and hash_left == get_hash(j, j + l - 1):
ans += 1
seen[l - 1].add(hash_left)
return ans
cpp 解法, 执行用时: 436 ms, 内存消耗: 7 MB, 提交时间: 2023-09-24 23:07:11
// 枚举
class Solution {
public:
int distinctEchoSubstrings(string text) {
int n = text.size();
unordered_set<string_view> seen;
string_view text_v(text);
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int l = j - i;
if (j * 2 - i <= n && text_v.substr(i, l) == text_v.substr(j, l) && !seen.count(text_v.substr(i, l))) {
++ans;
seen.insert(text_v.substr(i, l));
}
}
}
return ans;
}
};