首页 > 试题广场 >

计算重复字符串长度

[编程题]计算重复字符串长度
  • 热度指数:1607 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解
请从字符串中找出至少重复一次的子字符串的最大长度

输入描述:
字符串,长度不超过1000


输出描述:
重复子串的长度,不存在输出0
示例1

输入

ababcdabcefsgg

输出

3

说明

abc为重复的最大子串,长度为3
使用map<string,int>的数据结构存储,把所有可能的子字符串存储,遇到重复的时候会进行计数,最后再判断计数出来>1的字符串,比较长度。写之前觉得这种方***超时,没想到AC了。
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main() 
{
    string ss;
    cin >> ss;
    int len = ss.size();
    map<string, int> data;
    for (int m = 1; m < len; m++)
    {
        for (int i = 0; i < len - m; i++)
        {
            string s = ss.substr(i,m);
            data[s]++;
        }
    }
    int max = 0;
    for (auto c : data)
    {
        if (c.second > 1)
        {
            int temp = c.first.size();
            if (temp > max)
                max = temp;
        }
    }
    cout << max << endl;
    return 0;
}

发表于 2019-07-23 20:25:21 回复(0)
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
int main()
{
    string str;
    cin>>str;
    int len=str.length();
    vector<string> x;
    for(int i=0;i<len;i++)
    {
        for(int j=i;j<len;j++)
        {
                x.push_back(str.substr(i,j-i+1)); //存储所有子字符串
        }
    }
    sort(x.begin(),x.end()); //子字符串排序,重复的字符串一定相邻
    int n=x.size(),k=0;
    int arr[1000000]={0};
    for(int i=1;i<n;i++)
    {
        if(x[i]==x[i-1])
        {
            arr[k]=x[i].length();   //重复的子字符串长度存储
            k++;
        }
    }
    sort(arr,arr+k);
    cout<<arr[k-1]<<endl;  //输出排序最长的子字符串长度
}

发表于 2019-04-18 16:57:25 回复(0)
import java.util.*;

public class Main {
    private static final int INT_MAX = 0X3f3f3f3f;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String in = sc.next();
        int n = in.length();
        for (int len=n-1; len>=1; len--) {
            Set<String> set = new HashSet<>();
            for(int j=0; j<n-len; j++) {
                String s = in.substring(j, j + len);
                if (set.contains(s)) {
                    System.out.println(len);
                    return;
                }
                set.add(s);
            }
        }
        System.out.println(0);
    }
}
发表于 2019-02-15 11:43:20 回复(0)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();

        int res = 0, n = s.length();
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (s.substring(j, n).contains(s.substring(i, j))) {
                    res = Math.max(res, j - i);
                }
            }
        }
        System.out.println(res);
    }
}

发表于 2019-01-18 14:31:38 回复(0)
//计算重复字符串的长度
#include<bits/stdc++.h>
using namespace std;
int main()
{     string str;     int i,j,cnt,max,tempi,tempj;     while(cin>>str){         int len = str.length();         int *arr = new int[len];         for(i=0;i<len;i++){             arr[i]=0;         }         max = cnt = 0;         for(i=0;i<len-1;i++){             tempi=i;             for(j=tempi+1;j<len && tempi<len;j++){                 tempj = j;                 cnt = 0;                 if(str[tempi]==str[tempj]){                     while(str[tempi]==str[tempj]){                         tempi++;                         tempj++;                         cnt++;                     }                     if(arr[i]<cnt){                         arr[i]=cnt;                     }                 }else{                     tempi=i;                 }                 }         }         for(i=0;i<len;i++){             if(max<arr[i]) max = arr[i];         }         cout<<max<<endl;     }     return 0;
 } 

发表于 2018-08-07 20:17:02 回复(0)
package main

import (
    "fmt"
)

func main() {
    var s string
    fmt.Scan(&s)
    cnt:=map[string]int{}
    max:=0
    for i:=0;i<len(s);i++{
        for j:=i+max;j<len(s);j++{
            ss:=s[i:j]
            cnt[ss]++
            if cnt[ss]>1&&len(ss)>max{
                max=len(ss)
            }
        }
    }
    fmt.Print(max)
}

发表于 2023-03-19 08:24:21 回复(0)
菜鸡暴力解法
import java.util.*;

public class Main {
    public static void main(String[] args) {
        //input
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        
        //do work
        //找出所有子字符串对应的所有出现位置
        HashMap<String, List<Integer>> hashMap = new HashMap<>();
        for(int start=0; start<str.length(); start++) {
            for(int end=start+1; end<=str.length(); end++) {
                if(!hashMap.containsKey(str.substring(start, end))) {
                    hashMap.put(str.substring(start, end), new LinkedList<Integer>());
                }
                //最晚出现的位置在前
                hashMap.get(str.substring(start, end)).add(0, start);
            }
        }
        
        int ans = Integer.MIN_VALUE;
        for(int start=0; start<str.length(); start++) {
            for(int end=start+1; end<=str.length(); end++) {
                //寻找[end, str.length()]范围是否有[start, end]的重复
                if(hashMap.get(str.substring(start, end)).get(0)>start) {
                    ans  = Math.max(ans, end - start);
                }
            }
        }
        
        System.out.println(ans<0? 0: ans);
    }
}


发表于 2021-03-10 15:43:38 回复(0)
s=input()
n=len(s)
Set=set()
max_len=0
for i in range(n):
    for j in range(i+1,n):
        if s[i:j] not in Set:
            Set.add(s[i:j])
        else:
            max_len=max(max_len,len(s[i:j]))
print(max_len)

发表于 2020-07-23 18:09:01 回复(0)
// 1ms用时是什么体验?
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#define max(a, b) ((a) > (b) ? (a) : (b))
char* substr(char *str, int left, int right)
{
    char *res = (char *) malloc((right - left + 1) * sizeof(char));
    for (int i = left; i < right; ++i) {
        res[i - left] = str[i];
    }
    res[right - left] = '\0';
    return res;
}
bool find(char *str, char *sub)
{
    for (int  i = 0; i < strlen(str); ++i) {
        if (strncmp(str + i, sub, strlen(sub)) == 0) {
            return true;
        }
    }
    return false;
}
int main()
{
    char str[1001];
    scanf("%s", str);
    int maxlen = 0;
    int left, right;
    left = 0;
    right = 1;
    while (left <= right && right < strlen(str)) {
        char *s = substr(str, left, right);
        if (find(str + right, s)) {
            maxlen = max(maxlen, right - left);
            ++right;
        } else {
            ++left;
            if (left >= right) {
                ++right;
            }
        }
        free(s);
    }
    printf("%d\n", maxlen);
    return 0;
}

发表于 2020-07-15 19:37:13 回复(0)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        char[] carr = str.toCharArray();
        int[][] dp=new int[carr.length][carr.length];
        int i,j,max = 0;
        for(i=0;i<carr.length;i++) {
            if(carr[0]==carr[i]) {
                dp[i][0]=1;
                dp[0][i]=1;
                if(i!=0)
                max=1;
                
            }
            
        }
        for(i=1;i<carr.length;i++) {
            for(j=1;j<carr.length;j++) {
                
                if(carr[j]==carr[i]) {
                    dp[i][j]=dp[i-1][j-1]+1;
                    if(i!=j&&dp[i][j]>max) {
                        
                        max=dp[i][j];
                        
                    }
                    
                }
                
                
                
            }
            
            
        }
//        for(i=0;i<carr.length;i++)
//        System.out.println(Arrays.toString(dp[i]));
        
        System.out.println(max);

    }
}
发表于 2020-06-05 20:48:34 回复(0)
var str=readline();
var len=str.length;
// 子串长度
var mylen=Math.floor(len/2);
var tem=mylen;// 临时存储长度
var max=0;
// 子串长度至少为1,不存在则输出0
for(var i=0;i<=tem;i++){
    //console.log(mylen);
    for(var j=0;j<=len-2*mylen;j++){
        var mystr=str.slice(j,mylen+j);
        //console.log(mystr,(str.lastIndexOf(mystr)-str.indexOf(mystr)));
        if((str.lastIndexOf(mystr)-str.indexOf(mystr))>=mylen){
            //console.log(mystr.length);
            if(mystr.length>max){
                max=mystr.length;
            }
            break;
        }
    }
    mylen--;
}
console.log(max)

发表于 2020-03-18 18:49:12 回复(0)
//暴力求解
#include <iostream>
#include <string>
using namespace std;
int main(){
    string s;
    cin>>s;
    int max=0;
    for(int i=1;i<s.size()-1;i++){
        for(int j=0;j<=s.size()-i;j++){
            string s1=s;
            string s2=s1.substr(j,i);
            if(s1.find(s2)!=j){
                max=i;
            }
        }
    }
    cout<<max<<endl;
    return 0;
}
发表于 2020-02-03 15:21:30 回复(0)
var s = readline();
var max = 0;
for(var i = 0;i<s.length;i++){
    for(var j = i+1;j<s.length-1;j++){
        if(s.slice(j,s.length).indexOf(s.slice(i,j)) !== -1){
            if(max < (j-i)){
                max = j-i;
            }
        }
    }
}
print(max);

发表于 2019-09-02 11:32:03 回复(0)
//计算重复字符串长度
void naiveLRS(){
	string s;
	cin >> s;

	int n = s.size();
	map<string, int> m;
	int res = 0;
	for (int i = 0; i < n; i++){
		for (int j = 1; j <= n - i; j++){
			string tmp = s.substr(i, j);
			if (m.count(tmp)) res = max(res, j);
			else
				m[tmp]++;
		}
	}
	cout << res;
}

发表于 2019-09-01 19:15:11 回复(0)
#include <stdio.h>
#include <string.h>

#define MAXN 1010

int n;
char s[MAXN];

int main()
{
	int i,j,k,l,flag,max=0;
	gets(s);
	n = strlen(s);
	for(i=0;i^n;i++)
		for(j=i;j^n;j++)	//[i...j]
		{
			flag = 0;
			for(k=i+1;k<n & !flag;k++)
			{
				flag = 1;
				for(l=0;l<j-i+1;l++)
					if(s[k+l]^s[i+l])
					{
						flag = 0;
						break;
					}
			}
			if(flag & j-i+1>max)
				max = j - i + 1;	
		}
	printf("%d\n",max);
	return 0;
}

发表于 2019-08-19 10:38:12 回复(0)
while True:
    try:
        inp=input().strip()
        #print(inp)
        lenth=len(inp)
        #print(lenth)
        #max_num=1
        list1=[]
        for i in range(lenth-1,0,-1):
            for j in range(lenth-i):
                index1=inp[j:j+i]
                list1.append(index1)
        #print(list1)
        result=0
        for i in list1:
            if list1.count(i)>1:
                result=len(i)
                break
        print(result)

    except:
        break
编辑于 2019-07-27 21:04:03 回复(0)


s = input() t = 1 a = [] if len(s) == len(set(s)): print(0) else: 
		
    for i in range(len(s)):
a.append(len(s[t:i])) if s[t-1:i] in s[i:]: continue else: t=i print(max(a))

   
发表于 2019-04-15 18:36:47 回复(0)

import java.util.HashSet;
import java.util.Scanner;
 
public class Main {
     
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        String  st=scanner.nextLine();
        int max=0;
        int flag=0;
        HashSet<String > set=new HashSet<String>();
        for (int i = st.length()-1; i >=1; i--) {
            for (int j = 0; j < st.length()-i; j++) {
                if (!set.contains(st.substring(j, i+j))) {
                    set.add(st.substring(j, i+j));
                }
                else {
                    max=i;
                    flag=1;
                    break;
                }
            }
            set.clear();
            if (flag==1) {
                break;
            }
        }
         System.out.println(max);
    }
}
发表于 2019-03-29 20:21:03 回复(0)
s=input()
l=len(s)
res=0
a=[]
for i in range(1,l):
    for j in range(l-i+1):
        b=s[j:j+i]
        if b in a: 
            res=max(res,len(b))
            break
        else:
            a.append(b)
            continue
print(res)

发表于 2019-03-18 22:08:52 回复(0)