NC142. 最长重复子串
描述
示例1
输入:
"ababc"
输出:
4
说明:
abab为最长的重复字符子串,长度为4示例2
输入:
"abcab"
输出:
0
说明:
该字符串没有重复字符子串C++ 解法, 执行用时: 2ms, 内存消耗: 280KB, 提交时间: 2021-09-30
class Solution { public: //对具体的起点与长度,确认字符串是否为重复拼接形式 bool check(string& a, int len, int begin) { for(int i = begin; i < len + begin; ++i) { if(a[i] != a[i + len]) { //这说明字符串肯定不存在重复拷贝在其后面,返回false return false; } } return true;//这说明在这个字符串后面存在它的拷贝 } int solve(string a) { int n = a.length(); for(int i = n / 2; i > 0; --i) {//枚举长度 for(int j = 0; j <= n - i - i; ++j) {//枚举起点 //起点要保证两个字符串拼接后长度不会大于原字符串 if(check(a, i, j)) { return 2 * i;//说明找到了重复字符串,长度即为枚举长度两边 } } } return 0; } };
C++ 解法, 执行用时: 2ms, 内存消耗: 316KB, 提交时间: 2022-02-09
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param a string字符串 待计算字符串 * @return int整型 */ int solve(string a) { // write code here int n = a.size(); if (n == 0 || n == 1) return 0; for (int len = n / 2; len > 0; len--) { for (int i = 0; i + 2 * len <= n; i++) { int p1 = i, p2 = i + len; while (p1 < i + len) { if (a[p1] != a[p2]) break; p1++; p2++; } if (p1 == i + len) return 2 * len; } } return 0; } };
C++ 解法, 执行用时: 2ms, 内存消耗: 432KB, 提交时间: 2021-11-17
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param a string字符串 待计算字符串 * @return int整型 */ bool check(const string &s,int len,int begin){ for(int i = begin; i < begin + len; i++){ if(s[i] != s[i+len]) return false; } return true; } int solve(string a) { // write code here for(int i = a.size()/2; i > 0; i--) for(int j = 0; j < a.size()-i-i;j++){ if(check(a, i, j)) return i*2; } return 0; } };
C++ 解法, 执行用时: 3ms, 内存消耗: 304KB, 提交时间: 2021-10-20
class Solution { public: int solve(string a) { int n = a.length(), hyres = 0; for(int i = n / 2; i > 0; --i) { //枚举长度 for(int j = 0; j < n - i; ++j) { //枚举起点 if(a[j] == a[i + j]) { ++hyres; // 满足判断条件,hyres加一 } else { hyres = 0; // 不满足条件则重置长度 } if(hyres == i) return i * 2; } } return 0; } };
C++ 解法, 执行用时: 3ms, 内存消耗: 304KB, 提交时间: 2021-10-03
class Solution { public: int solve(string a) { int n = a.length(); int len = 0; for (int i = n/2; i > 0; --i) { // 枚举的长度 for (int j = 0; j < n-i; j++) { // 每次从头查找 if (a[j] == a[j+i]) { len++; } else { len = 0; } if (len == i) return i * 2; } } return 0; } };