判断两个String的交集，写个算法
判断两个String的交集
比如 A = "Marginle"，B = Valaienie", 交集为aie，写个算法。
请问这道题怎么做？
@薇酱的思路不错，我来实现
#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);
}
我就呵呵了， 这怎么看交集也不会是aie啊
你是想包含相同的字母的话也应该是 aein
用循环应该可以，分别获得A与B的length，总共需要比较A与B的长度之积次，用if判断就可以得到相同的字母，然后添加到一个集合中，希望我的回答对你有帮助
用循环应该可以，分别获得A与B的length，总共需要比较A与B的长度之积次，用if判断就可以得到相同的字母，然后添加到一个集合中，希望我的回答对你有帮助
来个简单的。
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
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());
}
}
这是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;
}
用两层循环,一次次判断,如果相同就将它添加到某个全局变量中。最后再用两层循环这个全局变量自身比较,不同话就添加,相同就添加一次
不知道你说的交集是什么意思。但是目测你需要的不是交集而是
最长公共子串 (英文: LCS)
一般是用动态规划算法，你可以自己google我说的关键字。