1

I need to make a program that prints the longest common sub-string out of two strings. for example: 

String str1 = "abcdef";
String str2 = "abcgef";

the longest common string should be "abc". I can only use loops, strings, and arrays! no methods/functions etc.. I'm a beginner and although I know functions I am not allowed to use it.

I tried using a count variable so that the last letter wont be compared to others chars from the second string over and over but the same error occurs.

String com = "";
String com2 = "";
int a;
int b;

for (i = 0; i < str1.length(); i++) {

    int count1 = 0;
    int count2 = 0;

    for (int j = 0; j < str2.length(); j++) {        
        a = i;
        b = j;
        com2 = "";

        while (str1.charAt(a) == str2.charAt(b)) {
            com2 = com2 + str1.charAt(a);                  

            if (com2.length()>com.length()) {              
                com = com2; 
            }     

            if (a<str1.length()-1) {       
                a++;  
            }

            if (b<str2.length()-1) {       
                b++;
            }                                   
        } 
    } 
} 

System.out.println(com);

like I said, the result should be "abc" and that's it, but I get a runtime error saying StringIndexOutOfBoundsException out of range 6.

thanks!

Stack Danny
  • 7,754
  • 2
  • 26
  • 55
HavingNoHead
  • 117
  • 1
  • 8
  • The code you posted has different compile-time errors. Please fix them and post a [MCVE](https://stackoverflow.com/help/mcve). – BackSlash Apr 10 '19 at 06:48
  • If your `String` consists of 3 characters (a, b and c), then the last accessible index of this `String` will be 2! – deHaar Apr 10 '19 at 06:48
  • 1
    You would help yourself and others if you indented the code correctly. – Andy Turner Apr 10 '19 at 06:53
  • [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173) – Andy Turner Apr 10 '19 at 06:58
  • You should also note that this wouldn't give the correct answer anyway, because you don't reset the value of `com2` before your while loop. – Andy Turner Apr 10 '19 at 07:13

6 Answers6

1

You have your exception because of you loop till a<str1.length() and b<str2.length(). You should change it to a<str1.length()-1. It happens because your string has length =6, but you start from 0. So the 6th element will be 5. Also, in while{} you have endless loop when a and b reach last index of str1 and str2, so, be carefull.

P.S.

You can change it to

public void method() {
    StringBuilder com = new StringBuilder();
    String str1 = "abcdef";
    String str2 = "abcgef";

    if (str1.length() == str2.length()) {
        for (int i = 0; i < str1.length() - 1; i++) {
            if (str1.charAt(i) == str2.charAt(i)) {
                com.append(str2.charAt(i));
                continue;
            } else {
                break;
            }
        }
        System.out.println(com);
    } else {
        System.out.println("They have different length");
    }
}
Dred
  • 1,076
  • 8
  • 24
  • That's wrong. `a – BackSlash Apr 10 '19 at 07:09
  • @BackSlash It has condition `if (a < str1.length() )` ,so while `a<6` that condition is true and then it happens `{a++;}` It means `a=5<6 => true => a++ => a=6 => while(str1.charAt(6) ==error` – Dred Apr 10 '19 at 07:12
  • length()-1 did solve the runtime error, but the program still does not work.. for example for strings "abcd" and "abc" it prints "abcbcc".. and for what i wrote in the post it doesnt print anything.. – HavingNoHead Apr 10 '19 at 07:14
  • @LiorRoz because you have endless while loop. – Dred Apr 10 '19 at 07:14
  • i solved it using what you said + putting the "String com2 = "";" line inside the inside loop. my bad – HavingNoHead Apr 10 '19 at 07:20
  • @LiorRoz, if you would add some char to String, or change String in future, it's better to use StringBuilder for not recreating new String for each char adding – Dred Apr 10 '19 at 07:29
0

You get an exception because you access str1.charAt(a) after incrementing a, without checking if it is still in bounds. Same for str2.charAt(b).

Change the while loop guard to:

while (a < str1.length() && b < str2.length() && str1.charAt(a) == str2.charAt(b))
Andy Turner
  • 137,514
  • 11
  • 162
  • 243
  • thanks, it does solve the error, but my program still doesnt work on certain strings, any idead why? for example strings "abcdef" and "abcgef" – HavingNoHead Apr 10 '19 at 08:20
0

Two mistakes on your code :

  1. You increment your while loop variables if they are lower than the associated string length. For str1 with a length of 6, if a is equal to 5, which is the last index of str1, you will have the StringIndexOutOfBoundsException (same on b / str2 )

  2. You don't reinitialize com2 at the end of the while loop

Your code should be :

String com = "";
String com2 = "";
int a;
int b;

for (i=0; i<str1.length(); i++) {

    int count1 = 0;
    int count2 = 0;

    for (int j=0; j<str2.length(); j++) {        

        a = i;
        b = j;

        while (str1.charAt(a) == str2.charAt(b)) { 
            com2 = com2 + str1.charAt(a);                  
            if (com2.length()>com.length()) {              
                com = com2; 
            }      
            if (a<str1.length() - 1) {
                a++;  
            }
            if (b<str2.length() - 1) {
                b++;  
            }                                   
        } 
        com2 = "";
     } 
} 
System.out.println(com);
SebVb
  • 187
  • 1
  • 3
  • 14
  • thanks, but it still only works on some strings.. on the strings "abcdef" and "abcgef" it doesnt do anything – HavingNoHead Apr 10 '19 at 08:05
  • @LiorRoz I haven't take the time to test all the configuraitons. Some little fix may made it works for all the strings (worked for "abcdefabc" and "abcgefabc", and worked". As i've made tests on a DotNetFiddle (don"'t have a java env availible just now :)), maybe I've made some mistakes while rewriting the code. Hope it helped a little :) – SebVb Apr 10 '19 at 08:19
  • still doesnt work for most strings, it seems that once the similar substrings are seperated by another char it just gets stuck.. – HavingNoHead Apr 10 '19 at 08:25
0
    public class Main
    {
      public static void main (String[]args)
      {
        String com = "";
        String com2 = "";
        String str1 = "bowbowbowbow";  // took the liberty of initializiating
        String str2 = "heloobowbowhellooo";
        int a;
        int b;

        for (int i = 0; i < str1.length (); i++)
          {
              // removed redundant declaration and initializiation of count 1 and count 2

        for (int j = 0; j < str2.length (); j++)
          {

            a = i;
            b = j;

            com2 = ""; // com2 should be made empty for each iteration

            while ( ( str1.charAt (a) == str2.charAt (b) ) && (a < str1.length() - 1 ) && ( b < str2.length() -1)  )
              {

            com2 = com2 + str1.charAt (a);
            if (com2.length () > com.length ())
              {
                com = com2;
              }

                a++;
                b++;

              }
          }
          }
        System.out.println (com);
      }

   }

Made some changes and have commented about it in the code. Seems to be working fine

Adwaith R Krishna
  • 766
  • 2
  • 8
  • 19
  • thanks, but the code only works on certain strings, for example-the strings you suggested does not work, any idead why? – HavingNoHead Apr 10 '19 at 08:15
  • your code prints "ab" instead of "abc", but when it comes to more complicated strings with different similiar substrings it doesnt work like mine – HavingNoHead Apr 10 '19 at 08:29
  • I have removed a print statement from the loop in the answer, I ran the code with complex strings and it seems to be working for me.. – Adwaith R Krishna Apr 10 '19 at 09:17
0

you look something like this.

String str1="abcdef";
    String str2="abcgefghj";
    String com = "";

    int min =Math.min(str1.length(), str2.length());

        for (int i =0; i< min ; i++) 
        {

              if(str1.charAt(i) == str2.charAt(i))
               {

                   com = com + str1.charAt(i);                     

               }
              else {
                  break;
              }

        }

        System.out.println(com);
Metin Bulak
  • 537
  • 4
  • 8
  • 30
0

as mentioned above there are some compile-errors (try to use an IDE, that helps). After cleaning those up, I made some changes and it should work:

    String str1 = "abcdef";
    String str2 = "abcgef";
    String com = "";
    String com2 = "";
    int a;
    int b;

    for (int i = 0; i < str1.length(); i++) {
    //counts removed (never used)
        for (int j = 0; j < str2.length(); j++) {
            a = i;
            b = j;
            com2 = ""; // Reset before start a new Check Loop
            while (str1.charAt(a) == str2.charAt(b)) {
                com2 = com2 + str1.charAt(a);
                if (com2.length() > com.length()) {
                    com = com2;
                }
                /**
                * length() goes from 0 (empty String) to n
                * index 0 is the first char in that String
                * so you need to adjust that (the simple way is -1)
                */
                if(a < str1.length()-1) {
                    a++;
                }
                if(b < str2.length()-1) {
                    b++;
                }
                //check for end of String -> Exit loop
                if(a >= str1.length()-1 && b >= str2.length()-1) {
                    break;
                }
            }
        }
    }
    System.out.println(com);
}
Jonny
  • 78
  • 1
  • 11
  • i think your additional last if statement made it work! ill continue to check but thanks! – HavingNoHead Apr 10 '19 at 08:48
  • You could also put the last if statement into the while check like others did here. Iam not so deep into java to tell you wich is better (performance). – Jonny Apr 11 '19 at 08:27