列表

详情


NC142. 最长重复子串

描述

定义重复字符串是由两个相同的字符串首尾拼接而成。例如:"abcabc" 是一个长度为 6 的重复字符串,因为它由两个 "abc" 串拼接而成;"abcba" 不是重复字符串,因为它不能由两个相同的字符串拼接而成。

给定一个字符串,请返回其最长重复子串的长度。

若不存在任何重复字符子串,则返回 0。

本题中子串的定义是字符串中一段连续的区间。

数据范围:字符串长度不大于 10^3,保证字符串一定由小写字母构成。
进阶:空间复杂度 ,时间复杂度

示例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;
    }
};

上一题