Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 6 of 6

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

  1. #1
    Junior Member
    Join Date
    Jan 2009
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Java program problem in identifying longest match sub string between two string

    my fellow programmer,
    i getting some problems with identifying the longest match substring between two string.
    so far i have this code.

     String FinalResult;
     
        public String match(String s1, String s2){
            for(int i = 0; i < s1.length(); i++){
                for (int j = 0; j < s2.length(); j++){
                    if (s1.charAt(i) != s2.charAt(j))
                        setFinalResult(FinalResult);
                    else                    
                        setFinalResult(Character.toString(s1.charAt(i)));
                }
     
            }
            String opt = new String(myStr);
            return getFinalResult();
        }
     
        public static void main(String args[]){
            longestSub mySub = new longestSub();
            System.out.println(mySub.match("hello", "hello"));
        }
     
        public String getFinalResult() {
            return FinalResult;
        }
     
        public void setFinalResult(String FinalResult) {
            this.FinalResult = FinalResult;
        }

    all help will be appreciated.
    Last edited by Deep_4; November 7th, 2012 at 01:07 PM.


  2. #2
    Junior Member
    Join Date
    Jan 2009
    Location
    uttarakhand,INDIA
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: longest match Substring between two Strings

    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

  3. #3
    mmm.. coffee JavaPF's Avatar
    Join Date
    May 2008
    Location
    United Kingdom
    Posts
    3,336
    My Mood
    Mellow
    Thanks
    258
    Thanked 287 Times in 225 Posts
    Blog Entries
    4

    Default Re: longest match Substring between two Strings

    Hello slick & hitesh_frnds,

    Welcome to the Java Programming Forums

    slick, there is a good tutorial here:

    http://www.javaprogrammingforums.com...explained.html
    Please use [highlight=Java] code [/highlight] tags when posting your code.
    Forum Tip: Add to peoples reputation by clicking the button on their useful posts.

    Looking for a Java job? Visit - Java Programming Careers

  4. #4
    mmm.. coffee JavaPF's Avatar
    Join Date
    May 2008
    Location
    United Kingdom
    Posts
    3,336
    My Mood
    Mellow
    Thanks
    258
    Thanked 287 Times in 225 Posts
    Blog Entries
    4

    Default Re: longest match Substring between two Strings

    Also, try this:

    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;
    }

    Algorithm implementation/Strings/Longest common substring - Wikibooks, collection of open-content textbooks
    Please use [highlight=Java] code [/highlight] tags when posting your code.
    Forum Tip: Add to peoples reputation by clicking the button on their useful posts.

    Looking for a Java job? Visit - Java Programming Careers

  5. #5
    Junior Member
    Join Date
    Jan 2009
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: longest match Substring between two Strings

    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.

  6. #6
    Junior Member
    Join Date
    Jan 2009
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: longest match Substring between two Strings

    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.

Similar Threads

  1. String substring, concatenation operation on linked list
    By oaks12 in forum Collections and Generics
    Replies: 1
    Last Post: January 15th, 2009, 07:12 AM
  2. Replies: 2
    Last Post: June 19th, 2008, 04:58 AM