题目
题目链接：
https://www.nowcoder.com/practice/4fe306a84f084c249e4afad5edf889cc
思路
注意：题目给的时间复杂度是O(N^2)
那么直接套用双重循环：外层循环i为假定起始重复子串的初始位置，
内层循环的j为假定重复子串的结束位置。注意，如果j-i为奇数，
那么不可能是重复子串，因此，每次把j的下标增加2。
由于我们是假定从i到j的子串为重复子串，因此我们需要去验证，
验证很简单，就是从中间截断，看前后两个串是否equals，
如果是重复子串，则直接更新最大长度即可。
Java代码
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param a string字符串 待计算字符串
* @return int整型
*/
public int solve (String a) {
//注意：题目给的时间复杂度是O(N^2)
//那么直接套用双重循环：外层循环i为假定起始重复子串的初始位置，
//内层循环的j为假定重复子串的结束位置。注意，如果j-i为奇数，
//那么不可能是重复子串，因此，每次把j的下标增加2。
//由于我们是假定从i到j的子串为重复子串，因此我们需要去验证，
//验证很简单，就是从中间截断，看前后两个串是否equals，
//如果是重复子串，则直接更新最大长度即可。
int ans = 0;
for (int i = 0; i < a.length() ; i++) {
for (int j = i; j <= a.length() ; j += 2) {
String s = a.substring(i, j);
if (s.length() % 2 == 1) continue;
boolean eq = s.substring(0, s.length() / 2).equals(s.substring(s.length() / 2));
if (eq) {
if (j - i > ans) {
ans = j - i;
}
}
}
}
return ans;
}
}
Go代码
package main
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param a string字符串 待计算字符串
* @return int整型
*/
func solve(a string) int {
//注意：题目给的时间复杂度是O(N^2)
//那么直接套用双重循环：外层循环i为假定起始重复子串的初始位置，
//内层循环的j为假定重复子串的结束位置。注意，如果j-i为奇数，
//那么不可能是重复子串，因此，每次把j的下标增加2。
//由于我们是假定从i到j的子串为重复子串，因此我们需要去验证，
//验证很简单，就是从中间截断，看前后两个串是否equals，
//如果是重复子串，则直接更新最大长度即可。
ans := 0
size := len(a)
for i := 0; i < size; i++ {
for j := i; j <= size; j++ {
if (j-i)%2 == 1 {
continue
}
s := a[i:j]
size1 := len(s)
s1 := s[0 : size1/2]
s2 := s[size1/2:]
if s1 == s2 {
if (j - i) > ans {
ans = j - i
}
}
}
}
return ans
}
C++代码
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param a string字符串 待计算字符串
* @return int整型
*/
int solve(string a) {
//注意：题目给的时间复杂度是O(N^2)
//那么直接套用双重循环：外层循环i为假定起始重复子串的初始位置，
//内层循环的j为假定重复子串的结束位置。注意，如果j-i为奇数，
//那么不可能是重复子串，因此，每次把j的下标增加2。
//由于我们是假定从i到j的子串为重复子串，因此我们需要去验证，
//验证很简单，就是从中间截断，看前后两个串是否equals，
//如果是重复子串，则直接更新最大长度即可。
int ans = 0;
for (int i = 0; i < a.size(); i++) {
for (int j = i; j <= a.size(); j++) {
if ((j - i) % 2 == 1) continue;
int L = i;
int m = (j - i) / 2;
int R = L + m;
while (R < j) {
if (a[L] == a[R]) {
L++;
R++;
} else {
break;
}
}
if (L >= m && R == j) {
if (j - i > ans) {
ans = j - i;
}
}
}
}
return ans;
}
};
