2 mrguanb MrGuanB 于 2015.05.29 15:34 提问

判断两个String的交集,写个算法

判断两个String的交集
比如 A = "Marginle",B = Valaienie", 交集为aie,写个算法。
请问这道题怎么做?

9个回答

gamefinity
gamefinity   Rxr 2015.05.29 16:53
已采纳

@薇酱的思路不错,我来实现

#include <stdio.h>
#include <string.h>

void main()
{
    char  r0[256];
    char  r1[256];
    char buff[1024];
    char *b0;
    int  i;

    memset(r0, 0, 256);
    puts("pls input the first string:");
    gets(buff);
    for (b0 = buff; *b0; b0++)
    {
        if (*b0 && !r0[*b0])
            r0[*b0] = 1;
    }
    memset(r1, 0, 256);
    puts("pls input the second string:");
    gets(buff);
    for (b0 = buff; *b0; b0++)
    {
        if (*b0 && !r1[*b0])
            r1[*b0] = 1;
    }

    for (i = 0; i < 256; i++)
        if (r0[i] && r1[i])
            putc(i, stdout);
    putc(0x0d, stdout);
}
qq_17246605
qq_17246605   2015.05.29 16:02

来个简单的。

1)先将AB都变为小写
2)申请个数组int a[26],数组内的数字全部先初始化为0.

3)遍历String A,那个字符出现就将对应位置置为1.(注意,是置为1),比如出现c,就置a['c'-'a']=1
4)遍历String B,哪个字符出现就将对应位置加一(这里是加一)

5)遍历数组a,输出值大于1的字符,比如a[2]=3,那么输出'a'+2=c

c601097836
c601097836 那个同一个字符串中出现相同的两个字符也要注意
大约 2 年之前 回复
danielinbiti
danielinbiti   Ds   Rxr 2015.05.29 16:09
 import java.util.HashMap;
import java.util.Iterator;

public class StringCmp {
    private HashMap<String,Integer> map = new HashMap();
    private int count = 0;//需要比较的字符串
    private boolean ignoreCap = false;//忽略大小写
    private HashMap tmpMap = new HashMap();//去掉一个字符串中重复的字符计数
    public StringCmp(){
        this(false);
    }
    public StringCmp(boolean ignoreCap){
        map.clear();
        this.count = 0;
        this.ignoreCap = ignoreCap;
    }
    public void putMap(String tsub){
        if(this.ignoreCap){
            tsub = tsub.toLowerCase();
        }
        if(tmpMap.get(tsub)==null){
            tmpMap.put(tsub, 1);
            Integer num = map.get(tsub);
            if(num==null){
                map.put(tsub+"", 1);
            }else{
                map.put(tsub+"",++num);
            }
        }
    }
    public void addString(String str){
        char tsub;
        tmpMap.clear();
        if(str!=null&&str.trim().length()>0){
            this.count++;
            for(int i=0;i<str.length();i++){
                tsub = str.charAt(i);
                this.putMap(tsub+"");
            }
        }
    }
    public String getISTion(){
        StringBuffer s = new StringBuffer();
        Iterator iter = map.keySet().iterator();
        while(iter.hasNext()){
            String key = (String)iter.next();
            if(map.get(key)==this.count){
                s.append(key);
            }
        }
        return s.toString();
    }
    public static void main(String[] args) {
        StringCmp sc = new StringCmp(false);
        sc.addString("Marginle");
        sc.addString("Valaienie");
        sc.addString("mdsA");
        System.out.println(sc.getISTion());
    }
}
u011467537
u011467537 这个写的不错
2 年多之前 回复
devmiao
devmiao   Ds   Rxr 2015.05.29 17:25

不知道你说的交集是什么意思。但是目测你需要的不是交集而是
最长公共子串 (英文: LCS)
一般是用动态规划算法,你可以自己google我说的关键字。

edouardzyc
edouardzyc   2015.05.29 15:38

我就呵呵了, 这怎么看交集也不会是aie啊
你是想包含相同的字母的话也应该是 aein

edouardzyc
edouardzyc 定义个list<char>, 把A的char都添加进去,遍历B所有的char,在list里面有就输出
大约 3 年之前 回复
qq_28404163
qq_28404163   2015.05.29 15:43

用循环应该可以,分别获得A与B的length,总共需要比较A与B的长度之积次,用if判断就可以得到相同的字母,然后添加到一个集合中,希望我的回答对你有帮助

qq_28404163
qq_28404163   2015.05.29 15:43

用循环应该可以,分别获得A与B的length,总共需要比较A与B的长度之积次,用if判断就可以得到相同的字母,然后添加到一个集合中,希望我的回答对你有帮助

ytt1361
ytt1361   2015.05.29 16:12

这是C++的,交集应该是aine吧!

 #include <iostream.h>
#include <iomanip.h>
#define MAX 99
//typedef char MM;
//自底向上地计算最优值
void LCSLength(int m,int n,char *x,char *y,int c[MAX][MAX],int b[MAX][MAX])
{
    int i,j;
    //当i=0或j=0时,空序列是Xi和Yj的最长公共子序列。
    for (i = 1; i <= m; i++) c[i][0] = 0;
    for (i = 1; i <= n; i++) c[0][i] = 0;
    for (i = 1; i <= m; i++)
    for (j = 1; j <= n; j++) {
     if (x[i]==y[j]) {
          c[i][j]=c[i-1][j-1]+1; b[i][j]=1;}
     else if (c[i-1][j]>=c[i][j-1]) {
          c[i][j]=c[i-1][j]; b[i][j]=2;}
     else { c[i][j]=c[i][j-1]; b[i][j]=3; }
     }
}
//构造最长公共子序列
void LCS(int i,int j,char *x,int b[MAX][MAX])//char *x:形参是指针变量
{
    if (i ==0 || j==0) return;

    if (b[i][j]== 1){ LCS(i-1,j-1,x,b); cout<<"<" <<x[i] << ">"; }
    else if (b[i][j]== 2) LCS(i-1,j,x,b);
    else LCS(i,j-1,x,b);
}
int main()
{
    int i,j,m,n;
    char x[MAX]={ ' ', ' '},y[MAX]={ ' ', ' '};
    int c[MAX][MAX]={0},b[MAX][MAX]={0};
    cout<<"**本程序可以求得字符数在99以内的任意两个字符串的最大公共子序列**\n ";
    cout<<"请输入第一个字符串的长度m= ";
    cin>>m;
    cout<<"请输入第一个字符串(“回车”结束)\n如果输入的字符数超过m,则会出错!\nx[" <<m<< "]= ";
    for(i=1;i<=m;i++)
        cin>>x[i]; //键盘输入x和y
    cout<< "请输入第二个字符串的长度n= ";
    cin>>n;
    cout<<"请输入第二个字符串\ny[" <<n << "]= ";
    for(i=1;i<=n;i++)
        cin>>y[i];
    LCSLength(m,n,x,y,c,b);
    cout << "c[m][n]中的内容:\n ";
    for(i=0;i <=m;i++)
    {
        for(j=0;j<=n;j++)
            cout <<c[i][j];
        cout <<endl;
    }
    cout <<"b[m][n]中的内容:\n ";
    for(i=1;i<=m;i++)
    {
        for(j=1;j<=n;j++)
            cout<<b[i][j];
        cout<<endl;
    }
    //构造最长公共子序列
    cout << "\nx[" <<m<< "]和y[" <<n<< "]的最长公共子序列为: ";
    LCS(m,n,x,b);
    cout << "\n " <<endl;
}

图片说明

u012216727
u012216727   Ds   Rxr 2015.05.29 17:00

用两层循环,一次次判断,如果相同就将它添加到某个全局变量中。最后再用两层循环这个全局变量自身比较,不同话就添加,相同就添加一次

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!