首页 > 试题广场 >

重复串查找

[编程题]重复串查找

热度指数：3355 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

一个重复字符串是由两个相同的字符串首尾拼接而成，例如abcabc便是长度为6的一个重复字符串，而abcba则不存在重复字符串。
给定任意字符串，请帮小强找出其中的最长重复子串。

输入描述:

输入一个字符串s，其中s长度小于1e4而且只包含数字和字母。

输出描述:

输出一个整数，表示s的最长重复子串长度，若不存在则输出0

示例1

输入

xabcabcx

输出

算法知识视频讲解

丸子姑娘啊

思想：重复子字符串的长度肯定是小于等于总长度的一半的，代码中用i来假设重复子字符串的长度，并用j来依次比对不同重复子字符串长度假设下实际重复情况。

#include<iostream>
using namespace std;
int main(){
    string input;
    cin>>input;
    int len=input.size();
    int output=0;
    for(int i=1;i<len/2;i++){
        int count=0;
        for(int j=0;j<len-i;j++){
            if(input[j]==input[j+i])
                count++;
            else count=0;
            if(count==i){
                output=max(output,count*2);
            }
        }
    }
    cout<<output;
    return 0;
}

发表于 2020-06-14 20:39:47 回复(17)

lalalei

python ac 解法，需要调整几个地方。

1. 间隔数 i 最好从大到小遍历

2. 增加 n - j <= 2 * i 的跳出内层循环条件

s = input().strip()
n = len(s)
def getnum(s, n):
    for i in range(n // 2, 0, -1):
        c = 0
        for j in range(0, n - i):
            if s[j] != s[j + i]:
                if n - j <= 2 * i:
                    break
                c = 0
            else:
                c += 1
                if c == i:
                    return c * 2
    return 0
print(getnum(s, n))

编辑于 2020-08-25 16:30:44 回复(2)

牛客892630169号

根据上面大佬的思路写了一个java的

import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        char[] a = str.toCharArray();
        int length = str.length();
        for (int i = length/2; i >0 ; i--) {
            int count = 0;
            for (int j = 0; j < length-i; j++) {
                if (a[j] == a[j+i]){
                    count++;
                }else{
                    count=0;
                }
                
                if (count == i){
                    System.out.println(count*2);
                    return ;
                }
            }
        }
        System.out.println(0);
    }
}

发表于 2020-08-24 20:49:12 回复(1)

pein531

记总字符串长度为n，从n/2开始滑动起点进行尝试，遇到前半段与后半段相等的字符串就退出，此时为最长的串

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] str = br.readLine().toCharArray();
        int maxLen = str.length / 2;
        loop: while(maxLen >= 0){
            int count = 0;
            for(int i = 0; i + maxLen < str.length; i ++){
                if(str[i] != str[i + maxLen]){
                    count = 0;
                }else{
                    count ++;
                    if(count == maxLen)
                        break loop;
                }
            }
            maxLen --;
        }
        System.out.println(Math.max(maxLen, 0) * 2);
    }
}

发表于 2021-11-22 17:39:04 回复(0)

CCXX201902121547196

从最大字符串s/2开始遍历，如果出现最大的则程序结束

#include<bits/stdc++.h>

using namespace std;
int main()
{
string str;
cin>>str;
int s=str.size();
for(int i=s/2;i>0;i--)
{
int count=0;
for(int j=0;j<s-i;j++)
{
if(str[i+j]==str[j])
count++;
else
count=0;
if(count==i)
{
cout<<2*i;
return 0;
}
}
}
cout<<0;
return 0;
}

发表于 2020-08-14 17:04:04 回复(0)

最喜欢春天的大菠萝很紧张

采用暴力解法，提供给大家，思路贼暴力，就是两次遍历，每次碰到s[i]和s[j]相同的情况就用while判断两个字符串是不是相同的。这个代码应该还可以优化，没优化的话会超过时间限制。

#include<iostream>
#include<string>
using namespace std;
class Solution
{
    public:
    int get_string(string s)
    {
        int max_res=0;
        for(int i=0;i<s.size();i++)
        {
             for(int j=i+1;j<s.size();j++)
             {
                 if(s[j]==s[i])
                 {
                    int f1=i,f2=j;
                     while(f1<j && f2<s.size())
                     {
                         if(s[f1]!=s[f2])
                         {
                             break;
                         }
                         else
                         {
                             f1++;
                             f2++;
                         }
                         
                     }
                    if(f1==j &&max_res<j-i)
                     max_res=j-i;
                 }
             }
        }
        return 2*max_res;
    }
    
};

int main()
{
    Solution S2;
    string s1;
    getline(cin,s1);
    auto len=S2.get_string(s1);
    cout<<len<<endl;
    return 0;
}

发表于 2020-06-23 17:58:30 回复(0)

COCO_641

测试用例 0101010

为什么4能通过，6过不了？？

发表于 2020-10-12 11:04:46 回复(2)

文艺小声

Matlab版本解法，就是不知道为什么ac30%，显示方法过于复杂，还有其他解法吗？求大神解答

try
while (1)
	a=input('','s');
    for i=fix(length(a)/2):-1:1
        n=0;
        for j=1:length(a)-i
            if a(j)==a(i+j)
                n=n+1;
                if n==i
                    b(n)=2*n;
                end
            else
                n=0;
            end
             if length(a)==length(unique(a))
                fprintf('%d\n',0);
               break
               end
        end
    end
    fprintf('%d\n',max(b));
    break           
end
catch
end

发表于 2020-09-27 11:44:09 回复(0)

牛客984698796号

def getMaxRepeatSubstringLength(s):
    length = len(s)
    for i in reversed(range(length//2)):
        count = 0
        for j in range(length - i):
            if s[j] == s[j+i]:
                count = count + 1
            else:
                if length - j <= 2 * i:
                    break
                count = 0
            if count == i:
                return count * 2
    return 0

s = input()
print(getMaxRepeatSubstringLength(s))

发表于 2020-09-10 16:02:03 回复(0)

牛客6150774号

python 70%通过打那么简单

str_input = input()

max = 0
for i in range(1, int(len(str_input)/2)+1):
    for j in range(len(str_input)-i):
        if str_input[j:j+i] == str_input[j+i:j+i+i]:
            max = i
            break
print(max*2)

发表于 2020-08-11 21:17:24 回复(1)

Python

我不想当大白菜

分析：使用不同长度去原句中遍历是否可行，对长度的搜索使用二分查找。AC80，有没有大佬给看看问题所在 :)

def check_valid(s,length):

    for i in range(len(s)):
        if i+length < len(s) and s[i] == s[i+length]:
            if i + length * 2 <= len(s):
                if s[i:i+length] == s[i+length:i+2*length]:
                    return True
    return False

def main():
    s = input()
    left,right = 0,len(s)//2+1
    max_length = 0
    while left <= right:
        mid = (left+right)//2
        if check_valid(s, mid): 
            max_length = max(max_length,mid)
            left = mid  + 1
        else:
            right = mid - 1

    return max_length*2 if 0 < max_length < len(s) else 0
print(main())

发表于 2020-07-07 20:57:02 回复(1)

bettermin

Python
60%通过，超时，建议使用二分查找 + Rabin-Karp 字符串编码 

def solve(s):
    n = len(s)
    res = 0
    # i表示重复子串的长度，则其范围在[1,n//2]
    for i in range(1,n//2+1):
        # 计数
        cnt = 0
        # 用长度为i的滑动窗口来遍历子串，若子串满足连续出现，则更新res
        for j in range(n-i):
            if s[j] == s[j+i]:
                cnt += 1
            else: cnt = 0
            if cnt == i: # 满足条件
                # print(s[j-i+1:j]) 重复子串
                res = max(res,cnt*2)
    return res

while True:
    try:
        s = input()
        print(solve(s))
    except:
        break

编辑于 2020-06-27 10:33:25 回复(0)