DS串应用—最长重复子串

本是古典何须时尚 2023-10-02 12:36 80阅读 0赞

### 题目描述 ###

> 求串的最长重复子串长度（子串不重叠）。例如：abcaefabcabc的最长重复子串是串abca，长度为4。

### 输入 ###

> 求串的最长重复子串长度（子串不重叠）。例如：abcaefabcabc的最长重复子串是串abca，长度为4。

### 输出 ###

> 对每个测试串，输出最长重复子串长度，若没有重复子串，输出-1.

### 样例输入 ###

3
    abcaefabcabc
    0szu0123szu1
    szuabcefg

### 样例输出 ###

4
    3
    -1

### 思路： ###

最简单的解法：从字符串的第一个位置开始，到s.length()/2，查找长度分别为1~len/2的子串能否在剩余的子串里找到。

### 实现代码： ###

#include <iostream>
    #include<string>
    using namespace std;
    
    int main() {
        int t;
        cin >> t;
        while (t--) {
            int i, j, zlen = -1;//默认-1
            string s;
            cin >> s;
            string temp;
            //取出长度分别为1~len/2的子串
            for (i = 1; i <= s.length() / 2; i++) {
                for (j = 0; j <= s.length() / 2; j++) {
                    temp = s.substr(j, i);//从j位置开始，长度为i的子串
                    if (s.find(temp, j + i) != -1)//长度分别为1~len/2的子串能否在剩余的子串里找到
                        zlen = i;//如果找到则长度更改
                }
            }
            cout << zlen << endl;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，80人围观）

还没有评论，来说两句吧...

相关阅读

相关 DS串应用—最长重复子串

题目描述 > 求串的最长重复子串长度（子串不重叠）。例如：abcaefabcabc的最长重复子串是串abca，长度为4。输入 > 求串的最长重复子串长度（子串不

本是古典何须时尚/ 2023年10月02日 12:36/ 0 赞/ 81 阅读

相关 LeetCode: 最长重复子串

参考网站：https://leetcode-cn.com/problems/longest-duplicate-substring/ 1. 题目描述给出一个字符串 S

约定不等于承诺〃/ 2023年05月28日 06:52/ 0 赞/ 81 阅读

相关 java最长重复子串

正文在下面，先打个广告： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly

桃扇骨/ 2022年12月25日 00:51/ 0 赞/ 246 阅读

相关 java 最长不重复子串,最长无重复字符子串

正文在下面，先打个广告： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly

谁借莪１个温暖的怀抱￠/ 2022年12月24日 15:59/ 0 赞/ 271 阅读

相关最长无重复子串

/ 求最长无重复子串 / public class Solution4 { public static void main(String[]

心已赠人/ 2022年10月29日 07:59/ 0 赞/ 294 阅读

相关最长连续无重复子串

代码一： -------------------- include <iostream> include <algorithm> using n

Dear 丶/ 2022年10月04日 12:53/ 0 赞/ 285 阅读

相关最长不重复子串（动态规划最长不重复子串+Hash）

题目1530：最长不重复子串时间限制：1 秒内存限制：128 兆特殊判题：否提交：1138 解决：373 题目描述：最长不重复子串就是从一个字符串中找到

布满荆棘的人生/ 2022年08月03日 05:24/ 0 赞/ 258 阅读

相关最长重复子串和最长不重复子串求解

1最长重复子串 1.1问题描述首先这是一个单字符串问题。子字符串R 在字符串L 中至少出现两次，则称R 是L 的重复子串。重复子串又分为可重叠重复子串和不可重

布满荆棘的人生/ 2022年07月13日 02:21/ 0 赞/ 311 阅读

相关最长重复子串

思路：使用后缀数组解决分析： 1、由于要求最长公共子序列，则需要找到字符串的所有子串，即通过产生字符串的后缀数组实现。 2、由于要求最长的重复子串，则需要对所有子串进行

刺骨的言语ヽ痛彻心扉/ 2022年06月17日 03:16/ 0 赞/ 305 阅读

相关最长不重复子串

1. 前言最近看了LeetCode上的一道题，想了很久才摸明白其中的逻辑，网站上有很多答题者提交了自己的代码，实现方式是多种多样，也包含很多种程序语言。因此，我这里记录

深碍√TFBOYSˉ_/ 2022年04月11日 03:24/ 0 赞/ 360 阅读