Saturday, March 12, 2011

f(a, b) returns string with only the characters found in both strings in the order of a


/* Write a function f(a, b) which takes two character string arguments and
* returns a string containing only the characters found in both strings in the
* order of a. Write a version which is order N-squared and one which is order N.
*/
public class StrOverlap {

public char[] overlapn2(char[] a, char[] b) {
char [] o = new char[a.length];
int k=0;
for(int i=0; i<a.length; i++) {
for(int j=0; j<b.length; j++) {
if (a[i] == b[j]) {
o[k++] = a[i];
break; // go to the next 'a'
}
}
}
for(; k<o.length; k++) {
o[k]= '\n';
}
return o;
}

public String overlapn(String b, String a, boolean showRepeats) {
StringBuffer result = new StringBuffer();
boolean[] asciiArr = new boolean[256]; // boolean ascii array (initially all false)
char[] aarr = a.toCharArray();
for (int i = 0; i < aarr.length; i++)
asciiArr[aarr[i]] = true;
char[] bbrr = b.toCharArray();
for (int i = 0; i < bbrr.length; i++)
if (asciiArr[bbrr[i]]) {
result.append(bbrr[i]);
if (!showRepeats) asciiArr[bbrr[i]] = false; // already printed
}
return result.toString();
}

public void init(String astr, String bstr) {
char []a = new char[astr.length()];
char []b = new char[bstr.length()];
astr.getChars(0, astr.length(), a, 0);
bstr.getChars(0, bstr.length(), b, 0);
char [] arr = overlapn2(a, b);
String stro = new String(arr);
System.out.println("o: \n"+stro);
String stron = overlapn(astr, bstr, true);
System.out.println("o: \n"+stron);
}

static public void main(String[] args) {
StrOverlap so = new StrOverlap();
if(args.length>1) {
so.init(args[0], args[1]);
} else {
System.out.println("usage: StrOverlap a b");
}
}

}

No comments:

Post a Comment