1 2 Previous Next 16 Replies Latest reply: Mar 30, 2010 12:31 PM by 3004 RSS

    Finding substring of a string

    843789
      hi, given a string S,how do i find the longest substring that appears at least twice in S (occurrences may overlap). ? how do i approach the problem?
        • 1. Re: Finding substring of a string
          796262
          What have you tried? What worked, what didn't work? How didn't it work?

          I doubt anybody here will do your homework for you.
          • 2. Re: Finding substring of a string
            843789
            i was thinking like this:
            finding the lenght of string ,then half it and finding a substring of this lenght that appear at least twice if none then reduce this length and recheck ,The problem i am facing is that how do find a substring of that lenght and how do i check if it is appearing at least twice?
            • 3. Re: Finding substring of a string
              796262
              streetfi8er wrote:
              i was thinking like this:
              finding the lenght of string ,then half it and finding a substring of this lenght that appear at least twice if none then reduce this length and recheck ,The problem i am facing is that how do find a substring of that lenght and how do i check if it is appearing at least twice?
              That approach is certainly possible using methods from the [String |http://java.sun.com/javase/6/docs/api/java/lang/String.html] class.
              • 4. Re: Finding substring of a string
                800606
                public static String getSubstring(String str){
                          Vector<String> substrings=new Vector<String>(),dupl=new Vector<String>();
                          for(int i=0;i<str.length();i++)for(int j=i+1;j<=str.length();j++){
                               String substr=str.substring(i,j);
                               if(substrings.contains(substr)==true)dupl.add(substr);
                               substrings.add(substr);
                          }
                          int max=0;
                          String maxstr="";
                          for(int i=0;i<dupl.size();i++){
                               String str1=dupl.elementAt(i);
                               if(str1.length()>max){
                                    max=str1.length();
                                    maxstr=str1;
                               }
                          }
                          return maxstr;
                     }
                • 5. Re: Finding substring of a string
                  796262
                  alexxzius wrote:
                  public static String getSubstring(String str){
                            Vector<String> substrings=new Vector<String>(),dupl=new Vector<String>();
                            for(int i=0;i<str.length();i++)for(int j=i+1;j<=str.length();j++){
                                 String substr=str.substring(i,j);
                                 if(substrings.contains(substr)==true)dupl.add(substr);
                                 substrings.add(substr);
                            }
                            int max=0;
                            String maxstr="";
                            for(int i=0;i<dupl.size();i++){
                                 String str1=dupl.elementAt(i);
                                 if(str1.length()>max){
                                      max=str1.length();
                                      maxstr=str1;
                                 }
                            }
                            return maxstr;
                       }
                  There is so much wrong with this code, starting with you attempting to post a full solution. You get an F- for the day.
                  • 6. Re: Finding substring of a string
                    800606
                    yeah, im tired of A's even though im no longer at school...
                    • 7. Re: Finding substring of a string
                      843789
                      alexxzius wrote:
                      public static String getSubstring(String str){
                                Vector<String> substrings=new Vector<String>(),dupl=new Vector<String>();
                                for(int i=0;i<str.length();i++)for(int j=i+1;j<=str.length();j++){
                                     String substr=str.substring(i,j);
                                     if(substrings.contains(substr)==true)dupl.add(substr);
                                     substrings.add(substr);
                                }
                                int max=0;
                                String maxstr="";
                                for(int i=0;i<dupl.size();i++){
                                     String str1=dupl.elementAt(i);
                                     if(str1.length()>max){
                                          max=str1.length();
                                          maxstr=str1;
                                     }
                                }
                                return maxstr;
                           }
                      Recursion is your friend:
                      public class LongestSubstringTwice {
                           private String s;
                      
                           public LongestSubstringTwice(String s) {
                                this.s = s;
                           }
                           public String longestSubstringTwice() {
                                return applySubstring(s);
                           }
                      
                           private String applySubstring(String sub) {
                                if(s.indexOf(sub) == -1)
                                     return "";
                                else if(s.indexOf(sub, s.indexOf(sub)+1) != -1)
                                     return sub;
                                String longest1 = applySubstring(sub.substring(0, sub.length()-1));
                                String longest2 = applySubstring(sub.substring(1));
                                if(longest1.length() >= longest2.length())
                                     return longest1;
                                else
                                     return longest2;
                           }
                      }
                      
                      public class LongestSubstringTwiceTest {
                           public static void main(String[] args) {
                                String s = "1234_1234_1234_";
                                System.out.println("s: " + s);
                                System.out.println("substring: " 
                                          + new LongestSubstringTwice(s).longestSubstringTwice());
                           }
                      }
                      • 8. Re: Finding substring of a string
                        796262
                        Is it free full solution day or something? You know you're actually hurting the OP (and, dare I say, the industry in general) by posting full solutions, right? That's not very nice.
                        • 9. Re: Finding substring of a string
                          800606
                          Well, my code has 1000s of errors, and the one below it uses OOP and recursion, which are advanced concepts for something like string manipulation. So, no correct solutions were actually provided...
                          • 10. Re: Finding substring of a string
                            843789
                            kevinaworkman wrote:
                            Is it free full solution day or something? You know you're actually hurting the OP (and, dare I say, the industry in general) by posting full solutions, right? That's not very nice.
                            He was asking for it, who am i to deny him the code -- if he plagiarizes it then that's his problem, why should I assume dishonesty from the start? I liked the problem so I solved it, I think the industry will recover...
                            • 11. Re: Finding substring of a string
                              843789
                              alexxzius wrote:
                              Well, my code has 1000s of errors, and the one below it uses OOP and recursion, which are advanced concepts for something like string manipulation.
                              That's what I was thinking -- if this was a class assignment and OP is an idiot then he'll use my code and get in trouble because the professor will be able to see right away it's not his code. If he's smart he'll go over it and figure out how it works and learn from it. I don't think I was hurting him by posting that code.
                              So, no correct solutions were actually provided...
                              I think my solution was correct. Advanced, yes, incorrect, no.
                              • 12. Re: Finding substring of a string
                                JosAH
                                streetfi8er wrote:
                                i was thinking like this:
                                finding the lenght of string ,then half it and finding a substring of this lenght that appear at least twice if none then reduce this length and recheck ,The problem i am facing is that how do find a substring of that lenght and how do i check if it is appearing at least twice?
                                Your solution doesn't work, e.g. the string "aaaaa" has two occurrences of the substring "aaaa"; your solution doesn't find them.

                                kind regards,

                                Jos
                                • 13. Re: Finding substring of a string
                                  3004
                                  fromrussiawithjava wrote:
                                  kevinaworkman wrote:
                                  Is it free full solution day or something? You know you're actually hurting the OP (and, dare I say, the industry in general) by posting full solutions, right? That's not very nice.
                                  He was asking for it, who am i to deny him the code -- if he plagiarizes it then that's his problem, why should I assume dishonesty from the start? I liked the problem so I solved it, I think the industry will recover...
                                  Wrong thinking.

                                  There's no excuse and no reason for giving a full code solution. Period.
                                  • 14. Re: Finding substring of a string
                                    3004
                                    streetfi8er wrote:
                                    i was thinking like this:
                                    finding the lenght of string ,then half it
                                    Won't work.
                                    XXXX
                                    Has two overlapping occurrences of
                                    XXX
                                    but you'll miss that if you start by cutting it in half.

                                    EDIT: Slower than Jos. Is anything more shameful? (Other than providing a full code solution, of course.)

                                    Edited by: jverd on Mar 30, 2010 10:30 AM
                                    1 2 Previous Next