Thread: Java program problem in identifying longest match sub string between two string

it will me more easier to u if u use Pattern & Matcher Classes in java

these are in java.util.regrex package

there is direct features available for these things
study these ,these r very interesting
and solve many problems related to strings matching

my fellow programmers,

thanks in advance for the wonder idea relpies.
i did try this method below

public int longestSubstr(String str_, String toCompare_) 
{
  if (str_.isEmpty() || toCompare_.isEmpty())
    return 0;
 
  int[][] compareTable = new int[str_.length()][toCompare_.length()];
  int maxLen = 0;
 
  for (int m = 0; m < str_.length(); m++) 
  {
    for (int n = 0; n < toCompare_.length(); n++) 
    {
      compareTable[m][n] = (str_.charAt(m) != toCompare_.charAt(n)) ? 0
          : (((m == 0) || (n == 0)) ? 1
              : compareTable[m - 1][n - 1] + 1);
      maxLen = (compareTable[m][n] > maxLen) ? compareTable[m][n]
          : maxLen;
    }
  }
  return maxLen;
}

unfortunately... this just return the length of the longest match.
which was fine.

however i did modify that method to output this...

public String LCS(String s1, String s2){
        LinkedList stores = new LinkedList();
        int LongStr = s1.length();
        int ShortStr = s2.length();
        int  [][] built = new int [LongStr + 1][ ShortStr + 1];
 
        for ( int i = LongStr - 1 ; i >= 0; i--){
            for(int j = ShortStr - 1 ; j >= 0; j--){
                if (s1.charAt(i) == s2.charAt(j))
                    built[i][j] = built [i + 1][j + 1] + 1;
                else
                    built[i][j] = Math.max(built[i+1][j], built[i][j+1]);
            }
        }
 
        int i = 0, j = 0;
        while(i < LongStr && j < ShortStr) {
            if (s1.charAt(i) == s2.charAt(j)) {
               myStr.append(s1.charAt(i));
 
                i++;
                j++;
            }
            else if (built[i+1][j] >= built[i][j+1]) i++;
            else     j++;
        }
        String opt = new String(myStr);
        return  opt;
 
    }

this now would return the length of the match in characters.. however if there were more matches..it will also include it....which is not i want. i just wanted the the longest match in charcters between the two string.

i also like the idea of the regrex... but as i was working over the few day... i did make some progress.
this is my new program.. the entire class.

public class longestString {
 
    String Short, Long;
    String Input1, Input2;
    StringBuffer myStr = new StringBuffer();
    Object testStr;
    LinkedList<String> newList = new LinkedList();
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
 
    public String LCM(String s1, String s2){
 
        int i = 0;
        int j = 0;
        while(i < s1.length() && j < s2.length()){
            if(s1.charAt(i) == s2.charAt(j)){              
               myStr.append(s1.charAt(i));
               j++;
            }
            else{
                if ( s1.charAt(i) != s2.charAt(j)){
                    i++;
                }
            }
        }
      String opt = new String(getMyStr());
       return  opt;
    }
 
    public LinkedList allCombinations(String givenStr){
        LinkedList myStrings = new LinkedList();
        for (int i = 0; i < givenStr.length(); i++){
            String newStr = givenStr.substring(i, givenStr.length());
            myStrings.add(newStr);            
        }
        return myStrings;
    }
 
    public LinkedList compare(LinkedList myList){
        while(!myList.isEmpty()){
            testStr = myList.pop();
            String thisStr = String.valueOf(testStr);
            newList.add(this.LCM(Long, thisStr));
 
        }
        return newList;
    }
 
    /** Creates a new instance of longestString */
    public longestString() throws IOException{
        System.out.println("please Enter the First String");
        Input1 = in.readLine();
        System.out.println("please Enter the Second String");
        Input2 = in.readLine();
 
         if (Input1.length() < Input2.length()){
            Short = Input1;
            Long = Input2;
        } else if (Input1.length() > Input2.length()){
            Long = Input1;
            Short = Input2;
        }else {
            Long = Input1;
            Short = Input2;
        }// end if-else statements
 
       // System.out.println("Long String = " + Long);
       // System.out.println("Short String = " + Short + '\n');
          System.out.println(compare(allCombinations(Short)));
       //System.out.println("Longest SubString is " + LCM(Long,Short));
     }
 
    public StringBuffer getMyStr() {
        return myStr;
    }
 
    public void setMyStr(StringBuffer myStr) {
        this.myStr = myStr;
    }
 
}

now to follow this...what it does is that it takes two strings.. the second string it breaks it up into all permutations and then compare it to the first. it would then suppose to return a list of all the matches it finds in both strings..
for example if the first string were hello and the second were mello.. this what the program will actually do.

please Enter the First String
hello
please Enter the Second String
mello
[mello, ello, llo, lo, o]
as you can see it gives me all the possible permutations of mello to campare to hello.
if i compare them now it suppose to return alist of all matches, example; ello would match, hence ello would be return.
this is actuall happen, but the problem now is that the program is appending the mathces and returning the result.
example;
please Enter the First String
hello
please Enter the Second String
mello
[, ello, ellollo, ellollolo, ellolloloo]
so u would see now that ello was matched, then llo but it was added on to ello first before returning.. this is where i got stuck..
i think the problem is with the LCM method.
that is

public String LCM(String s1, String s2){
 
        int i = 0;
        int j = 0;
        while(i < s1.length() && j < s2.length()){
            if(s1.charAt(i) == s2.charAt(j)){              
               myStr.append(s1.charAt(i));
               j++;
            }
            else{
                if ( s1.charAt(i) != s2.charAt(j)){
                    i++;
                }
            }
        }
      String opt = new String(getMyStr());
       return  opt;
    }

would appreciat any futher help again.