给你一个字符串 text ,请你返回满足下述条件的 不同 非空子字符串的数目: 可以写成某个字符串与其自身相连接的形式(即,可以写为 a + a,其中 a 是某个字符串)。 例如,abcabc 就是 abc 和它自身连接形成的。用java
时间: 2024-05-13 14:18:09 浏览: 84
可以使用哈希表来记录每个子字符串出现的次数,然后遍历一遍字符串,对于每个子字符串,判断它是否可以写为某个字符串与其自身相连接的形式。如果是,就累加它出现的次数。
具体实现如下:
```java
public int countSubstrings(String text) {
int n = text.length();
Map<String, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
String sub = text.substring(i, j);
map.put(sub, map.getOrDefault(sub, 0) + 1);
}
}
int ans = 0;
for (Map.Entry<String, Integer> entry : map.entrySet()) {
String sub = entry.getKey();
int count = entry.getValue();
if (count > 1 && isConcatenation(sub)) {
ans += count;
}
}
return ans;
}
private boolean isConcatenation(String s) {
int n = s.length();
for (int i = 1; i <= n / 2; i++) {
if (n % i != 0) {
continue;
}
String sub = s.substring(0, i);
boolean isValid = true;
for (int j = i; j < n; j += i) {
if (!s.substring(j, j + i).equals(sub)) {
isValid = false;
break;
}
}
if (isValid) {
return true;
}
}
return false;
}
```
其中,isConcatenation 函数用于判断一个字符串是否可以写为某个字符串与其自身相连接的形式。具体实现是,枚举可能的重复段长度 i,如果字符串长度能够被 i 整除,就判断每个长度为 i 的子段是否相等。如果都相等,就说明这个字符串可以写为某个字符串与其自身相连接的形式。
阅读全文