1 2 Previous Next 16 Replies Latest reply on Mar 30, 2010 6:51 PM by JosAH

# Finding substring of a string

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
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
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
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
``````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);
}
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
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);
}
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
yeah, im tired of A's even though im no longer at school...
• ###### 7. Re: Finding substring of a string
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);
}
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;
}``````
``````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
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
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
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
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
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
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
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