每日一题8

Question

求两字符串的公共子串，如abc123与123456的公共字串为123

Answer 1

所有的比如123abc789和abcd123公共字串有123 和 abc

Answer 2

应该是所有的最长公共符串吧  难倒 
比如123abc789和abcd123公共字串 包括 1 2 3 12 13 123 a b c  ab abc ....???

Answer 3

那重新出吧？这个题目非常简单，对于Java来说。

Answer 4

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class testPublicString{
    private static final char Space = ' ';
    Set<String> commonChildStrSet;    public testPublicString(String str1,String str2){
        str1=getPrefix(str2.length())+str1;        commonChildStrSet=new HashSet<String>();
        for(int i=0;i<str1.length();i++){
            String childStr=getSubString(str1,i, str2.length());
            String commonStr=getCommonString(childStr,str2);
            commonChildStrSet.addAll(getSplitResult(commonStr));
        }
    }
    public List<String> getSplitResult(String str){
        List<String> ls=new ArrayList<String>();
        
        str=str.trim();
        
        String[] arr=str.split("\\s+");
        for(String tmp:arr){
            if(tmp.length()>0){
                ls.add(tmp);
            }
        }
        
        return ls;
    }
    private String getPrefix(int n){
        StringBuffer sb=new StringBuffer();
        for(int i=0;i<n;i++){
            sb.append(Space);
        }
        
        return sb.toString();
    }
    public String getCommonString(String op1,String op2){
        StringBuffer sb=new StringBuffer();
        
        for(int i=0;i<op1.length();i++){
            char c1=op1.charAt(i);
            char c2=op2.charAt(i);
            
            sb.append(c1==c2?c1:Space);
        }
        
        return sb.toString();
    }
    private String getSubString(String str,int startIndex,int length){
        String strTmp=str.substring(startIndex);    
        int n=strTmp.length();
        return strTmp.substring(0, length>n?n:length);
    }
    
    public Set<String> getCommonChildStrSet() {
        return commonChildStrSet;
    }
    public static void main(String[] args){
        String test1="abc123";
        String test2="123456";
        testPublicString commonChildString=new testPublicString(op1,op2);
        // run result:
        System.out.print(test1+"和"+test2+"的匹配字串有：");
        for(String tmp:commonChildString.getCommonChildStrSet()){
            System.out.print(tmp+",");
        }
        System.out.print("\n");
    }
}

Answer 5

上一个不完整import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class testPublicString{
    private static final char Space = ' ';
    Set<String> commonChildStrSet;    public testPublicString(String str1,String str2){
        str1=getPrefix(str2.length())+str1;        commonChildStrSet=new HashSet<String>();
        for(int i=0;i<str1.length();i++){
            String childStr=getSubString(str1,i, str2.length());
            String commonStr=getCommonString(childStr,str2);
            commonChildStrSet.addAll(getSplitResult(commonStr));
        }
    }
    public List<String> getSplitResult(String str){
        List<String> ls=new ArrayList<String>();
        
        str=str.trim();
        
        String[] arr=str.split("\\s+");
        for(String tmp:arr){
            if(tmp.length()>0){
                ls.add(tmp);
            }
        }
        
        return ls;
    }
    private String getPrefix(int n){
        StringBuffer sb=new StringBuffer();
        for(int i=0;i<n;i++){
            sb.append(Space);
        }
        
        return sb.toString();
    }
    public String getCommonString(String op1,String op2){
        StringBuffer sb=new StringBuffer();
        
        for(int i=0;i<op1.length();i++){
            char c1=op1.charAt(i);
            char c2=op2.charAt(i);
            
            sb.append(c1==c2?c1:Space);
        }
        
        return sb.toString();
    }
    private String getSubString(String str,int startIndex,int length){
        String strTmp=str.substring(startIndex);    
        int n=strTmp.length();
        return strTmp.substring(0, length>n?n:length);
    }
    
    public Set<String> getCommonChildStrSet() {
        return commonChildStrSet;
    }
    public static void main(String[] args){
        String test1="abc123";
        String test2="123456";
        testPublicString commonChildString=new testPublicString(test1,test2);
        // run result:
        System.out.println("run result:");
        System.out.print(test1+"和"+test2+"的匹配字串有：");
        for(String tmp:commonChildString.getCommonChildStrSet()){
            System.out.print(tmp+",");
        }
        System.out.print("\n");
    }
}

Answer 6

10L 的测试了下 貌似在          String test1="abc123";
        String test2="123abc1456";
得到的结果是：abc123和123abc1456的匹配字串有：abc1,123,

Answer 7

abc123和123abc1456的公共字串为abc1,123，有什么不对吗？

Answer 8

public class TCS02 { /**
 * @param args
 */
public static void main(String[] args) {
// TODO Auto-generated method stub
TCS02 tcs = new TCS02();
String str1 = "abc123324234324";
String str2 = "123456abc123324234324";
int xx = str2.indexOf("12");
List<String> allSub = tcs.run(str1, str2);
for(String s:allSub){
System.out.println(s);
}
} public  List<String> run(String str1 ,String str2){
List<String> allSub = new LinkedList<String>();
int l = str1.length();
for(int i = 0;i<l;i++){
String lastsubString = null;
for(int j=i+2;j<=l;j++){
String substr = str1.substring(i,j);
boolean match = str2.indexOf(substr)>-1;
if(!match && lastsubString != null){
allSub.add(lastsubString);
lastsubString = null;
}else if( match){
lastsubString = substr;
}
}
if(lastsubString!= null){
allSub.add(lastsubString);
i = i+ lastsubString.length();
}
}
return allSub;
}
}

Answer 9

18楼代码纠正
public class TCS02 { /**
 * @param args
 */
public static void main(String[] args) {
// TODO Auto-generated method stub
TCS02 tcs = new TCS02();
String str1 = "abc123324234324x43232234";
String str2 = "123456abc123324234324d43232234";
int xx = str2.indexOf("12");
List<String> allSub = tcs.run(str1, str2);
for(String s:allSub){
System.out.println(s);
}
} //全部查找
public  List<String> run(String str1 ,String str2){
List<String> allSub = new LinkedList<String>();
int l = str1.length();
for(int i = 0;i<l;i++){
String lastsubString = null;
for(int j=i+2;j<=l;j++){
String substr = str1.substring(i,j);
boolean match = str2.indexOf(substr)>-1;
if(!match && lastsubString != null){
allSub.add(lastsubString);
lastsubString = null;
}else if( match){
lastsubString = substr;
}
}
if(lastsubString!= null){
allSub.add(lastsubString);
i = i+ lastsubString.length();
}
}
allSub = pro(allSub);
return allSub;
}

//处理重复
private List<String> pro(List<String> subs){

for(int i=0;i<subs.size()-1;i++){
for(int j=i+1;j<subs.size();j++){
if(subs.get(j).indexOf(subs.get(i))>-1 ){
subs.remove(i);
i--;
break;
}else if(subs.get(i).indexOf(subs.get(j))>-1 ){
subs.remove(j);
j--;
}
}
}
return subs;
}
}
自己小测了一下
如果还不对，求删回复。

Answer 10

不是最好的算法，但是比较简单的：
  public static void main(String[] args) {
    String str1 = "xabcd1234xyza";
    String str2 = "abcd134xyz";
    for (int length = Math.min(str1.length(), str2.length()); length > 0; length--) {
      Set<String> set1 = split(str1, length);
      Set<String> set2 = split(str2, length);
      set1.retainAll(set2);
      if (!set1.isEmpty()) {
        System.out.println(set1);
        return;
      }
    }
  }
  
  static Set<String> split(String str, int length) {
    int size = str.length() - length + 1;
    Set<String> set = new HashSet<String>(size);
    for (int i = 0; i < size; i++) {
      set.add(str.substring(i, i + length));
    }
    return set;
  }

Answer 11

完善了一下，测试一下吧大家import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
public class testPublicString{
    private static final char Space = ' ';
    Set<String> commonChildStrSet;    public testPublicString(String str1,String str2){
        str1=getPrefix(str2.length())+str1;        commonChildStrSet=new HashSet<String>();
        for(int i=0;i<str1.length();i++){
            String childStr=getSubString(str1,i, str2.length());
            String commonStr=getCommonString(childStr,str2);
            commonChildStrSet.addAll(getSplitResult(commonStr));
        }
    }
    public List<String> getSplitResult(String str){
        List<String> ls=new ArrayList<String>();
        
        str=str.trim();
        
        String[] arr=str.split("\\s+");
        for(String tmp:arr){
            if(tmp.length()>0){
                ls.add(tmp);
            }
        }
        
        return ls;
    }
    private String getPrefix(int n){
        StringBuffer sb=new StringBuffer();
        for(int i=0;i<n;i++){
            sb.append(Space);
        }
        
        return sb.toString();
    }
    public String getCommonString(String op1,String op2){
        StringBuffer sb=new StringBuffer();
        
        for(int i=0;i<op1.length();i++){
            char c1=op1.charAt(i);
            char c2=op2.charAt(i);
            
            sb.append(c1==c2?c1:Space);
        }
        
        return sb.toString();
    }
    private String getSubString(String str,int startIndex,int length){
        String strTmp=str.substring(startIndex);    
        int n=strTmp.length();
        return strTmp.substring(0, length>n?n:length);
    }
    
    public Set<String> getCommonChildStrSet() {
        return commonChildStrSet;
    }
    public static void main(String[] args){
     System.out.println("run!Please input two Strings!");
     System.out.print("Input the First String:");
     Scanner test001 = new Scanner(System.in);
      String test1=test001.nextLine();
      String test2 = "";
     if(test1 == null || test1.trim().equals("")) {
      System.out.println("Wrong!");
}else {
System.out.print("Input the Second String:");
     Scanner test002 = new Scanner(System.in);
     test2=test002.nextLine();
     if(test2 == null || test2.trim().equals("")) {
         System.out.println("Wrong!");
    }else{
 testPublicString commonChildString=new testPublicString(test1,test2);
        // run result:
        System.out.println("run result:");
        System.out.print(test1+"和"+test2+"的匹配字串有：");
        for(String tmp:commonChildString.getCommonChildStrSet()){
            System.out.print(tmp+",");
        }
        }
}
    
       
       
       
        System.out.print("\n");
    }
}

Answer 12

如果这样的话用后缀数组就可以，从底往上推的话可以到n*log(n)

Answer 13

测试用例：
String str1 = "String str1 = abc123324234324";
String str2 = "String str2 = 123456abc123324234324";
貌似只能找出一个

Answer 14

对啊，str1完全包含在str2里面，当然只有1个最大长度的共通字符串，你想要多少啊？

Answer 15

String str1 = "String str1 = abc123324234324";
String str2 = "String str2 = 123456abc123324234324";的公共字符串是不是应该包含"String str"和" = "呢？

Answer 16

如果要所有，把我那个return去掉就万事大吉了...

Answer 17

拆分成字符，依次遍历再合成string。

Answer 18

如果不用连续的话 用DP就可以写出LCS
如果是连续的 用后缀数组就行

Answer 19

package CSDN;import java.util.ArrayList;
import java.util.List;/**
 * 求两字符串的公共子串(连续的公共子串)
 * @author xqh
 *
 */
public class FindSubstring {
public static void main(String[] args) {
String str1 = "abc123456ff";
String str2 = "123789abcdff";
String s = "";
String[] subString;
List<Character> list = new ArrayList<Character>();
char[] ch = str2.toCharArray();
for (char c : str1.toCharArray())
list.add(c);
for (int i = 0; i < ch.length; i++) {
if (list.contains(ch[i])) {
s += ch[i];
} else {
s += " ";
continue;
}
}
subString = s.split(" ");
for (String str : subString)
System.out.print(str + " ");
}
}
结果：123 abc ff 

Answer 20

很多方法啊，我也写个吧。
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;public class Test2 { /**
 * 获取子字符串，以set形式返回
 * @param str
 * @return
 */
public Set getSubStringSet(String str)
{
char[] chs = str.toCharArray();
Set set = new HashSet();
for(int i=0;i<str.length();i++)
{
for(int j=1;j<=str.length()-i;j++)
{
set.add(String.valueOf(chs, i, j));
}
}
return set;
}
/**
 * @param args
 */
public static void main(String[] args) {
// TODO Auto-generated method stub
String str1 = "abc123";
String str2 = "xabc1233ab";

Test2 t = new Test2();
//获取子字符串
Set set1 = t.getSubStringSet(str1);
Set set2 = t.getSubStringSet(str2);
int s1 = set1.size();
int s2 = set2.size();
//保留在大集合中的
boolean b =s2>s1?set2.retainAll(set1):set1.retainAll(set2);
if(b)
{
Set set = s2>s1?set2:set1;
//输出
for (Iterator it = set.iterator(); it.hasNext();) {
String name = (String) it.next();
System.out.println(name);
}
}
}}

Answer 21

测试用例：
String str1 = "DXBabc123456ff";
String str2 = "DXB123789abcdff";貌似输出为：
DXB123
abc
ff

Answer 22

输出为：
abc123
c
a
c1
ab貌似。。

Answer 23

用类似后缀数组的方法写了一个求最长的。
using System;
using System.Collections.Generic;namespace Robot
{
    class Program
    {
        class Suffix
        {
            public int Start;
            public int End;
            public int Index;
            public int Length
            {
                get { return End - Start + 1; }
            }            public Suffix(int s, int e, int index)
            {
                Start = s;
                End = e;
                Index = index;
            }            public string GetString(string item, int length)
            {
                return item.Substring(Start, length);
            }
        }        static void Main(string[] args)
        {
            string[] items = new string[] {"abc123ijkl", "123456ijkl" };
            List<Suffix> suffixs = new List<Suffix>();            for (int i = 0; i < items.Length; i++)
            {
                for (int j = 0; j < items[i].Length; j++)
                {
                    Suffix suf = new Suffix(j, items[i].Length - 1, i);
                    suffixs.Add(suf);
                }
            }            suffixs.Sort(delegate(Suffix a, Suffix b)
            {
                int length = Math.Min(a.Length, b.Length);
                for (int i = 0; i < length; i++)
                    if (items[a.Index][a.Start + i] != items[b.Index][b.Start + i])
                        return items[a.Index][a.Start + i] - items[b.Index][b.Start + i];                return a.Length - b.Length;
            });            int max = 0;
            string result = null;            for (int i = 1; i < suffixs.Count; i++)
            {
                if (suffixs[i].Index != suffixs[i - 1].Index)
                {
                    int mLength = 0;
                    int length = Math.Min(suffixs[i].Length, suffixs[i - 1].Length);                    for (int j = 0; j < length; j++)
                    {
                        char a = items[suffixs[i].Index][suffixs[i].Start + j];
                        char b = items[suffixs[i - 1].Index][suffixs[i - 1].Start + j];
                        if (a == b)
                            mLength++;
                        else
                            break;
                    }                    if (mLength > max)
                    {
                        result = suffixs[i].GetString(items[suffixs[i].Index], mLength);
                        max = mLength;
                    }
                }
            }            Console.WriteLine(result);
            Console.ReadKey();
        }
    }
}

Answer 24

不是求全部的嘛！
4楼：
应该是所有的最长公共符串吧 难倒 
比如123abc789和abcd123公共字串 包括 1 2 3 12 13 123 a b c ab abc ....???是滴，熊猫兄

Answer 25

对39#代码的改进，欢迎熊猫兄的测试！！！package CSDN;import java.util.ArrayList;
import java.util.List;/**
 * 求两字符串的公共子串(连续的公共子串)
 * @author xqh
 *
 */
public class FindSubstring {
public static void main(String[] args) {
String str1 = "subabc123789dffeee";
String str2 = "subjj123eekabcdff";
char[] ch = str2.toCharArray();
String s = "";
List<Character> list = new ArrayList<Character>();
for (char c : str1.toCharArray())
list.add(c);
int index = 0;
while (index < ch.length) {
if (list.contains(ch[index])) {
for (int indexList = list.indexOf(ch[index]); indexList < list.size(); indexList++) {
if (list.get(indexList) == ch[index]) {
s += ch[index];
index++;
if (index >= ch.length)
break;
} else {
s += " ";
break;
}
}
} else
index++;
}

String[] subString = s.split(" ");
for (String str : subString)
System.out.print(str + " ");
}
}输出结果为：
sub 123 ee abc dff 

Answer 26

再次补充一下，上面的代码少了一句：s += " ";
package CSDN;import java.util.ArrayList;
import java.util.List;/**
 * 求两字符串的公共子串(连续的公共子串)
 * @author xqh
 *
 */
public class FindSubstring {
public static void main(String[] args) {
String str1 = "subabc123789dffeeexx";
String str2 = "subjjx123eekabcdff";
char[] ch = str2.toCharArray();
String s = "";
List<Character> list = new ArrayList<Character>();
for (char c : str1.toCharArray())
list.add(c);
int index = 0;
while (index < ch.length) {
if (list.contains(ch[index])) {
for (int indexList = list.indexOf(ch[index]); indexList < list.size(); indexList++) {
if (list.get(indexList) == ch[index]) {
s += ch[index];
index++;
if (index >= ch.length)
break;
} else {
s += " ";
break;
}
}
s += " ";
} else
index++;
}

String[] subString = s.split(" ");
for (String str : subString)
System.out.print(str + " ");
}
}输出结果：
sub  x  123  ee  abc  dff 

Answer 27

class FindSubPublicString
{
public FindSubPublicString(String str)
{
this.str = str;
}

public List<String> getSubPublicString(String another)
{
List<String> ls = null;
if (another != null && str != null)
{
List<Character> lc = new ArrayList<Character>();
for (char ch : str.toCharArray())
{
lc.add(ch);
}

ls = new LinkedList<String>();
for (int index = 0; index < another.length(); ++index)
{
int indexof = lc.indexOf(another.charAt(index));
if (indexof != -1)
{
ls.add(getSubString(str.substring(indexof), another.substring(index)));
}
}
}
return ls;
} private String getSubString(String substring, String another)
{
StringBuffer sb = new StringBuffer();
char[] sub = substring.toCharArray();
char[] ano = another.toCharArray(); for (int index = 0; index < sub.length && index < ano.length
&& sub[index] == ano[index]; ++index)
{
sb.append(sub[index]);
}
return sb.toString();
}

public void setString(String newStr)
{
str = newStr;
} private String str;
}public class Hello
{
public static void main(String[] args)
{
String str = "abcdefg";
String another = "a1abcdegfgg";
List<String> ls = new FindSubPublicString(str).getSubPublicString(another);
if (ls != null)
{
for (String s : ls)
{
System.out.println(s);
}
}
}
}

Answer 28

直接使用正则表达式处理/*
*求两字符串的公共子串，如abc123与123456的公共字串为123
*@date:2011-05-24
*/import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.ArrayList;public class Test{
public static void main(String[] args){
String str1 = "abc123";
//----> result:123
//str1 = abc123dd123456 -- > result:123456
String str2 = "123456";
String result = getMatcherCharacter(str1,str2,"-");
System.out.println(result);
} public static String getMatcherCharacter(String str1,String str2,String separation){
//注意这里的separation如果采用了元字符需要进行转义
if(str1.contains(separation) || str2.contains(separation)){
throw new RuntimeException("either" + "'" + str1 + "' or '" + str2 + "'  contains '" + separation + "'" );
}
String content = str1 + separation + str2;
String regex = ".*?(.+).*" + separation + ".*(\\1).*";
Pattern pattern = Pattern.compile(regex);
Matcher matcher = pattern.matcher(content);
String result = "";
int end = 0;
while(matcher.find(end)){
if(result.length() <= matcher.group(1).length()){
result = matcher.group(1);
}
end = matcher.end(1);
//System.out.println(end);
}
return result;
}
}

Answer 29

题目的意思应该是所有能尽量连在一起的最大字符，要不就不可能是123，而是1,2,3,12，…………
可以用下面的代码/*
*求两字符串的公共子串，如abc123与123456的公共字串为123
*@date:2011-05-24
*/import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.ArrayList;public class Test{
public static void main(String[] args){
String str1 = "abc123";
//----> result:123
//str1 = abc123dd123456 -- > result:123456
String str2 = "123456";
ArrayList<String> result = getMatcherCharacter(str1,str2,"-");
int i = 1;
for(String s : result){
System.out.println(i ++ + ":" + s);
}
} public static ArrayList<String> getMatcherCharacter(String str1,String str2,String separation){
//注意这里的separation如果采用了元字符需要进行转义
if(str1.contains(separation) || str2.contains(separation)){
throw new RuntimeException("either" + "'" + str1 + "' or '" + str2 + "'  contains '" + separation + "'" );
}
String content = str1 + separation + str2;
String regex = ".*?(.+).*" + separation + ".*(\\1).*";
Pattern pattern = Pattern.compile(regex);
Matcher matcher = pattern.matcher(content);
ArrayList<String> result = new ArrayList<String>();
int end = 0;
while(matcher.find(end)){
result.add(matcher.group(1));
end = matcher.end(1);
}
return result;
}
}

Answer 30

从长到短遍历，看起来代码循环比较多，但是大多情况下没几次就出来了
public class ChongfuString {
public static void main(String[] args) {
 String test1="asdasasdabc123";
         String test2="123abc1";
ha:{for (int i = 0; i < test1.length(); i++) {
for (int j = 0; j < i; j++) {
String s1 =test1.substring(j, test1.length()-i+j+1);
if (test2.split(s1,2).length==2) {
System.out.println(s1);
break ha;
}
}
}}
}
}

Answer 31

方法不错，我的思想也与你的差不多，只不过我直接用的string ，不如你用的char[]效率好。 你的算法不支持字符串有空格，建议把你的s+=" " 修改为直接将s存放到一个list里，因为你的输出时split(" ")会把你定义的空格分隔符和字符串中本身可能有的空格都认为是空格分隔符。

Answer 32

#include<iostream>
int n,m;
char t1[5000],t2[5000];
bool used[1010][1010];
int rec[1010][1010],ls[1010][1010];int max(int a,int b)
{
 if(a>b)return a;   
 return b;   
}int f(int a,int b)
{
if(a>n||b>m)return 0;
if(used[a][b])return rec[a][b];
used[a][b]=true;
int tmp=0,tt=0;
if(t1[a]==t2[b]){tmp=f(a+1,b+1)+1;ls[a][b]=1;}    
tt=f(a+1,b);
if(tt>tmp){tmp=tt;ls[a][b]=2;}
tt=f(a,b+1);
if(tt>tmp){tmp=tt;ls[a][b]=3;}  
rec[a][b]=tmp;
return rec[a][b];
}void lj(int a,int b)
{
if(a>n||b>m)return;
if(ls[a][b]==1){printf("%c ",t1[a]);lj(a+1,b+1);}         
if(ls[a][b]==2)lj(a+1,b);
if(ls[a][b]==3)lj(a,b+1);     
}int main(void)
{
freopen("1.txt","r",stdin);
freopen("2.txt","w",stdout);
    
  scanf("%s",&t1[1]);
   n=strlen(&t1[1]);
  
  scanf("%s",&t2[1]);
   m=strlen(&t2[1]);int mm=f(1,1);//DP ---LCS
printf("%d\n",mm);  
lj(1,1); //输出路径 
return 0;
}

Answer 33

测试例子1：String str1 = "123789";
String str2 = "123-123789";
输出按理只有一个123789，而你的有两个123 123789测试例子二：String str1 = "DXB1-abcdef-123-456-ff-";
String str2 = "DXB1+123+789abcd+ff+abcdef+";
你的输出为:DXB1 1 23 abcd f f abcdef 
这个就让人看不怎么懂了

Answer 34

严蔚敏的数据结构好像有讲这个kmp模式匹配算法学习～