今天在网上看到有一道算法题目:
求N个字符串中的最大公子串
http://www.iteye.com/topic/1118325
刚好闲着,做之。
先说一下思路:
1、从N个字符串中找出最小的字符串
2、分解出最小字符串最大公字符串列表:
例如:abcde
--------------------
abcde
abcd
bcde
abc
bcd
cde
ab
bc
cd
de
----------------------
3、分解出来的公子串从上到下去匹配其他的字符,都能匹配成功则是所要查找的最大公子串
4、如果同时存在两个相等长度的公子串 则以最先发现的为最大
说完上代码:
import java.nio.Buffer;
import java.nio.CharBuffer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
/**
* 求N个字符串中的最大公子串
*思路:
* 1、从N个字符串中找出最小的字符串
* 2、分解出最小字符串最大公字符串列表:
* 例如:abcde
* --------------------
* abcde
* abcd
* bcde
* abc
* bcd
* cde
* ab
* bc
* cd
* de
* ----------------------
* 3、分解出来的公子串从上到下去匹配其他的字符,都能匹配成功则是所要查找的最大公子串
* 4、如果同时存在两个相等长度的公子串 则以最先发现的为最大
*
*/
public class MaxPublicStr {
class Combination {
private CharBuffer a(char[] a, int[] tempNum, int m, int n, int startInd) {
for (int i = 0; i < n; i++) {
if (i >= startInd && i < (m + startInd)) {
tempNum[i] = 1;
} else {
tempNum[i] = 0;
}
}
return createResult(a, tempNum, m);
}
/**
* @param a:组合数组
* @param m:生成组合长度
* @return :所有连续的组合数组列表
*/
public List<CharBuffer> combinationsequence(char[] a, int m) {
List<CharBuffer> list = new ArrayList<CharBuffer>();
int n = a.length;
// 生成辅助数组。首先初始化,将数组前n个元素置1,表示第一个组合为前n个数。
int[] tempNum = new int[n];
for (int i = 0; i < tempNum.length; i++) {
if (i + m > n) {
break;
}
list.add(a(a, tempNum, m, n, i));
}
return list;
}
// 根据辅助数组和原始数组生成结果数组
@SuppressWarnings("unchecked")
public CharBuffer createResult(char[] a, int[] temp, int m) {
CharBuffer bos = CharBuffer.allocate(m);
for (int i = 0; i < a.length; i++) {
if (temp[i] == 1) {
bos.put(a[i]);
}
}
return bos;
}
}
public List<CharBuffer> combinationsequence(String str, int m) {
char[] a = str.toCharArray();
Combination c = new Combination();
List<CharBuffer> list = c.combinationsequence(a, m);
return list;
}
//字符串列表中的最短字符串
public String minStr(List<String> strings) {
return Collections.min(strings, new Comparator<String>() {
public int compare(String str1, String str2) {
if (str1.length() < str2.length())
return -1;
else if (str1.length() == str2.length())
return 0;
else if (str1.length() > str2.length())
return 1;
return 0;
}
});
}
//判断字符串列表中的每个字符串是否包含指定字符串,如果有一个不包含就返回false
public boolean contains(List<String> strings, String str) {
for (String s : strings) {
if (!s.contains(str))
return false;
}
return true;
}
public String maxSubString(List<String> strings) {
String shortStr = minStr(strings);
int i = shortStr.length();
//i是1 而不是0 因为当只有一个字符串的时候就没最大可言
while (i > 1) {
List<CharBuffer> list = combinationsequence(shortStr, i);
for (CharBuffer charBuffer : list) {
Buffer tempstr = charBuffer.rewind();
if (contains(strings, tempstr.toString())) {
return tempstr.toString();
}
}
i--;
}
return null;
}
public static void main(String[] args) {
MaxPublicStr max = new MaxPublicStr();
ArrayList<String> strings = new ArrayList<String>(Arrays.asList("ababcdghy", "abcdeftdsfgsdg", "abcdefsdf"));
String publicStr = max.maxSubString(strings);
System.out.println(publicStr);
}
}
分享到:
相关推荐
求N个字符串中的最大公子串(华为技能鉴定题) C语言版,可以参考
求N个字符串的最长公共子串,N,字符串长度不超过255。例如N=3,由键盘依次输入3个字符串为 Whatislocalbus? Namesomelocalbuses. loca1busisahighspeedI/Obusclosetotheprocessor. 则最长公共子串为“local...
有一个共N个字符的字符串,存放在buff的存储区中,在字符串中查找“空格”(ASCII码为20h)字符,找到则在屏幕上输出FOUND!,没有找到则输出NOT FOUND!。
C语言编程-编写函数fun求一个字符串的长度,在main函数中输入字符串,并输出其长度;
两个字符串中最大相同的子串。 "qwerabcdtyuiop" "xcabcdvbn
C++实现找出两个字符串中最大的公共子串
求两个字符串的最长公共字符串 输出全部位置信息,并输出字符串,相同字符串先输出所有位置信息在输出字符串 测试平台:XP/VS 2008 CN
求一个字符串中字母的个数,以及一个字符串中数字的个数,相对于用C语言能更好地实现了算法的利用率的最大化,省去了C语言中用指针来定义字符串的环节,从来让程序变得更加整洁,易懂。
给定 n 个字符串,在这 n 个字符串中有相同的字符串,不同的字符串只有 num 个。要求首先输 入字符串的个数 n,然后输入 n 个字符串,将这 n 个字符串中 num 个不同的字符串按照字典序排序, 并输出每个字符串在这 n...
C语言程序设计-编写函数fun(str,i,n),从字符串str中删除第i个字符开始的连续n个字符(注意str[0]代表字符串的第一个字符);.c
有三个字符串,找出其中最大者
传入一个字符串和整数m,将此字符串中从第m个字符开始的全部字符复制成为另一个字符串并打印出来。
本文实例讲述了C语言求两个字符串的最长公共子串的方法。分享给大家供大家参考。具体实现方法如下: #include "stdio.h" #include "string.h" #include "stdlib.h" void getCommon(char str1[],char str2[],char * ...
在随意给出的2个字符串中,找出它们共同的最长的子串。 【输入】 输入文件的第一行为一个整数2,接下来有2行,每行为一个字符串,每个字符串的长度均小于255。 【输出】 输出只有一行,即:共同的最长子串,若有多个...
找出两个字符串中最大公共子字符串,如"abccade","dgcadde"的最大子串为"cad" 主要用的是矩阵的思想
【问题描述】编写函数itob(n,s,b),用于把整数n转换成以b为基的字符串并存储到s中. 编写程序,使用函数itob(n,s,b)将输入的整数n,转换成字符串s,将s输出.转换后的字符串从最高的非零位开始输出。如果n为负数,则输出的...
必须实现如下操作,字符串比较、求串的长度、判断串是否为空、将串置空、字符串赋值(包括两个字符串类复制,一个字符串赋值到CmyString对象)、求字符串中的一个字符或改变字符串中的一个字符(采用重载[]),...
这个代码,可以删除一个字符串中你想删除的字符或字符串
编写程序:从键盘上输入一个包含10个字符的字符串,把该字符串与程序中给定的字符串("bacdbcabca") //依次比较,统计两个字符串对应字符相等的数目。然后输出从键盘上输入的字符串, //并把两个字符串中对应字符不...
aaa,bbb,ccc n=2时 截取结果 bbb 很明白了吧 哈