`
zhongkem
  • 浏览: 152459 次
  • 性别: Icon_minigender_1
  • 来自: 天津
社区版块
存档分类
最新评论

求字符串的最长不重复子串

阅读更多

题目要求:找到一个字符串中的一个连续子串,这个子串内不能有任何两个字符是相同的,
并且这个子串是符合要求的最长的。
例如:abcdeab,这个字符串有很多不重复子串,比如:abcde, bcdea, cdeab都是不重复子串,
而且都是最长的。
//试验例子 abceaefk  abceaaaaaa

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
public class LongestsubString {

	public static void main(String[] args) {
		print(getLongestNoRepeatSubString("abceafb"));

	}
	private static void print(List list) {
		for(Iterator it=list.iterator();it.hasNext();){
			System.out.println(it.next());
		}
		
	}
	public static List getLongestNoRepeatSubString(String src){
		char[] arr=src.toCharArray();
		int len=arr.length;//数组长
		List<String> subList=new ArrayList<String>();//最长的子串可能会有多少,用这个临时保存
		int max;//最长子段长度
		int start;//最长子段的开始位置
		Map<Character,Integer> charMap=new HashMap();//保存对应字符及其最后出现的位置		
		max=start=0;
		int i;
		for(i=0;i<len;i++){
			if(!charMap.containsKey(arr[i])){//不包含的话就加入到map中
				charMap.put(arr[i], i);				
			}else{//包含的话就得处理了,看在重复出现前的子串是否是更长
				int pre=charMap.get(arr[i]);			
				int tempLen=i-start;//当前子串长度							
				if(tempLen>=max){//找到新的最长子串了
					if(tempLen>max)subList.clear();//需要刷新列表
					max=tempLen;
					subList.add(src.substring(start, i));//保存这个最长子串					
					charMap.put(arr[i], i);//置成新的位置					
				}else{									
					charMap.put(arr[i], i);//置成新的位置
				}
				start=pre+1;//只要重复了,都得重新开始设置start的位置
			}
		}	
		if(i-start>=max){//这个主要是处理这种情况:abcd 没有重复的~~
			if(i-start>max)subList.clear();
			subList.add(src.substring(start, i));
		}
		return subList;
	}
}

 

分享到:
评论
1 楼 MCQCM 2016-04-22  
你的代码有个小问题,不信,你试试abceaefkbn。正确如下:


import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
public class LongestsubString {

public static void main(String[] args) {
print(getLongestNoRepeatSubString("abceabfkbn"));

}
private static void print(List list) {
for(Iterator it=list.iterator();it.hasNext();){
System.out.println(it.next());
}

}
public static List getLongestNoRepeatSubString(String src){
char[] arr=src.toCharArray();
int len=arr.length;//数组长
List<String> subList=new ArrayList<String>();//最长的子串可能会有多少,用这个临时保存
int max;//最长子段长度
int start;//最长子段的开始位置
Map<Character,Integer> charMap=new HashMap();//保存对应字符及其最后出现的位置
max=start=0;
int i;
for(i=0;i<len;i++){
if(!charMap.containsKey(arr[i])){//不包含的话就加入到map中
charMap.put(arr[i], i);
}else{//包含的话就得处理了,看在重复出现前的子串是否是更长
int pre=charMap.get(arr[i]);
if(pre<start)
continue;
int tempLen=i-start;//当前子串长度
if(tempLen>=max){//找到新的最长子串了
if(tempLen>max)subList.clear();//需要刷新列表
max=tempLen;
subList.add(src.substring(start, i));//保存这个最长子串
charMap.put(arr[i], i);//置成新的位置
}else{
charMap.put(arr[i], i);//置成新的位置
}
start=pre+1;//只要重复了,都得重新开始设置start的位置
}
}
if(i-start>=max){//这个主要是处理这种情况:abcd 没有重复的~~
if(i-start>max)subList.clear();
subList.add(src.substring(start, i));
}
return subList;
}
}



相关推荐

    在字符串中查找最长重复子串的探讨

    ### 在字符串中查找最长重复子串的探讨 #### 背景与问题定义 本篇文章主要探讨了如何在给定的字符串中找到最长的重复子串。例如,在字符串 "t1t1" 中,最长重复子串为 "t1";而在 "cabcabca" 中,最长重复子串可以...

    寻找字符串中不包含重复字符的最长子串

    这个问题的目标是找出给定字符串中的最长子串,这个子串中的所有字符都不重复。这是一个在编程面试和算法竞赛中常见的问题,尤其与动态规划、滑动窗口和哈希映射等技术有关。 描述 "在字符串中找到最长的不包含重复...

    python实现求两个字符串的最长公共子串方法

    在Python编程语言中,求解两个字符串的最长公共子串是一项常见的字符串处理任务。这个问题的解决方案通常基于动态规划思想,即将问题分解为更小的子问题,并存储子问题的解以便于后续使用,从而避免重复计算。下面...

    Python简单实现查找一个字符串中最长不重复子串的方法

    本文实例讲述了Python简单实现查找一个字符串中最长不重复子串的方法。分享给大家供大家参考,具体如下: 刚结束的一个笔试题,很简单,不多说简单贴一下具体的实现: #!usr/bin/env python #encoding:utf-8 ''''' ...

    Manacher's ALGORITHM_ O(n)时间求字符串的最长回文子串 - Blog of Felix021 - Tec

    Manacher's 算法是一种高效解决字符串中最长回文子串问题的算法,它能在O(n)的时间复杂度内完成,其中n是字符串的长度。这个算法由Manacher在1975年提出,主要利用了回文串的对称性质来减少不必要的重复计算。 首先...

    求串中最长重复子串。

    在计算机科学领域,“求串中最长重复子串”是一个常见的字符串处理问题。假设有一个字符串S,我们的任务是找出其中最长的重复子串,即在S中至少出现两次的最长连续子序列。这个问题不仅涉及到字符串匹配的基本概念,...

    寻找字符串中最长的回文子串的长度

    本问题关注的是寻找一个字符串中最长的回文子串及其长度。回文子串是指一个字符串,从前往后读和从后往前读完全相同,例如"madam"和"level"都是回文。 解决这个问题可以使用多种算法,其中最著名的可能是Manacher's...

    求字符串中出现相同且长度最长字符串

    总结来说,解决“求字符串中出现相同且长度最长字符串”的问题,我们可以运用滑动窗口、哈希映射或动态规划等技术。在实际编程中,应根据数据规模和性能要求选择合适的方法。对于给定的示例字符串,最终输出应为...

    C++实现找出两个字符串中最大的公共子串

    在编程领域,字符串操作是常见的任务之一,尤其是在算法设计和数据处理中...通过理解并掌握这种动态规划解决方案,可以扩展到处理更复杂的问题,比如寻找多个字符串的最大公共子串或者最长公共子序列(不连续的子串)。

    Python实现针对给定字符串寻找最长非重复子串的方法

    给定一个字符串,例如"abcabcd",我们要找出其中最长的不重复子串。在这个例子中,最长的非重复子串是"abc",因为它在原字符串中只出现了一次。 为了实现这个功能,我们可以采用以下步骤: 1. **滑窗切片(slice_...

    python 实现给定一个字符串,找出不含有重复字符的最长子串的长度

    # 给定一个字符串,找出不含有重复字符的最长子串的长度 # 示例 1: # 输入: "abcabcbb" # 输出: 3 # 解释: 无重复字符的最长子串是 "abc",其长度为 3 # 示例 2: # 输入: "bbbbb" # 输出: 1 # 解释: 无重复字符的...

    无重复字符的最长子串 给定一个字符串 s ,请你找出其中不含有重复字符的 最长 子串的长度

    无重复字符的最长子串 给定一个字符串 s ,请你找出其中不含有重复字符的 最长 子串的长度。

    给定一个字符串,求出其最长的重复子串(腾讯2011年10月15日校招笔试)

    根据给定的文件信息,本篇文章将详细解析“给定一个字符串,求出其最长的重复子串”这一算法问题。此题目源自于腾讯2011年10月15日的校园招聘笔试,主要考察应试者对字符串处理、排序及模式匹配等算法的理解与应用...

    查找最长公共子串

    动态规划解决方案通常涉及构建一个二维数组dp,其中dp[i][j]表示字符串a的前i个字符和字符串b的前j个字符的最长公共子串的长度。初始化时,dp[0][j]和dp[i][0]都为0,因为没有字符与空字符串的公共子串长度为0。 接...

    输出最长子串的代码

    在编程领域,"最长子串"通常是指在一个或多个字符串中找到共享的、最长的连续字符序列。这个概念广泛应用于文本处理、数据挖掘以及算法竞赛等场景。在本例中,我们将探讨如何编写一个程序来找出给定字符串集合中的...

    php-leetcode题解之无重复字符的最长子串.zip

    这个问题是LeetCode中的第3题,也被广泛地称为“最长不重复字符的子串”。在本文中,我们将深入探讨这个问题,了解其背后的算法思想,并通过PHP代码进行详细解析。 无重复字符的最长子串问题的核心在于寻找字符串中...

    查询出字符串中重复出现且最长的子字符串

    在编程领域,寻找字符串中重复出现且最长的子字符串是一个常见的字符串处理问题。这个任务涉及到字符串操作、算法设计以及可能的动态规划或滑动窗口等技术。以下将详细阐述这个问题的解决方案及其相关知识点。 首先...

    java求字符串的正向反向最大公共字符串

    总结来说,解决"java求字符串的正向反向最大公共字符串"这个问题,我们可以采用动态规划方法,通过对字符串的遍历和比较,找出并返回最长的公共子串。这种技术在处理字符串匹配、编辑距离等问题时非常常见,有助于...

    js代码-(算法)(字符串)找最大不重复子串

    在JavaScript编程中,找最大不重复子串是一个常见的字符串处理问题,主要涉及到算法设计和字符串操作。这个问题的目标是找到一个字符串中的最长子串,这个子串中的字符都不重复。这在许多实际应用中都有用到,例如...

Global site tag (gtag.js) - Google Analytics