Here is a problem,

String : CATDOGCATFISH

The function should return the number of times the pattern repeats (2 in
above string) if it finds a 3 letter pattern (in this case CAT) . The
pattern may be anyhere in the string.

Another ex : ABCATCDCATDOCAT expected retunrn 3 CAT
DEFDOGDOGXZ expected retunrn 3 DOG

All usual assumptions can be made .. String is terminated, can use all
regular Java functions, libs etc.
HOW CAN I DO THIS
could anybody help me with the code and explaination i am a beginer in java

This appears to be homework. if it is work set as part of an educational program, please do not request help. it is there for you to learn and understand for yourself, not for someone to do for you.

this problem is harder than you probably think it is.

read up on string searching. some good algorithms are: knuth-morris-pratt, boyer-moore, and rabin-karp. these are pretty advanced.

a simpler way would be to use brute force. i personally wouldn't do this, but it sounds like you're desperate and / or have no idea what you're doing here. it's very easy, very inefficent, and very stupid.

if i and j match, they are incremented, otherwise j is reset (to start from the beggining of the pattern), and i is set to move where we start looking over one.

when we get out of the loop, if j has moved through the entire pattern, it's in there, so we return where it is. if not, we return the length of the string to indicate we went all the way through and didn't find anything.

now could use this algorithm, but this requires that you have a pattern to search for. so you could also have a function to build all possible substrings of the string recursively, and check each pattern. also, if the pattern occurs more than once, you're screwed unless you modify that to keep track of how many times / where it is located.

that should get you started. good luck.

look at knuth-morris-pratt, it's pretty cool.

hi there i wrote this code which works fine for three letter string search
but any one has better logical program plz tell me
i would be greatfull


import java.util.*;

class parseString
{

void findRepeat(String s)
{
LinkedList l = new LinkedList();

String a = s.toUpperCase();
String b = null;

int j=3;
int count = 0;

for ( int i=0; i < a.length()-2; i++)
{
try
{
b = a.substring(i,j);
l.add(b);
j+=1;
}

catch(Exception e)
{

}

}

System.out.println("=============================================");

System.out.print("Input String is :" + s + "\n");


Iterator iter = l.iterator();

while(iter.hasNext())
{
System.out.print(iter.next() + "-->");
}

TreeSet to = new TreeSet();

for(int i=0; i < l.size();i++)
{
for(int k=0; k < l.size(); k++)
{
if( l.get(i).equals(l.get(k)) )
{
count= count + 1;
}
}

if(count > 1 )
{
to.add(l.get(i) +" "+count);
}
count=0;
}

if (!to.isEmpty()){
System.out.println("Repeating Patterns");
System.out.println(to);
}
else
{
System.out.println("No Repeating Patterns Found!");
}
System.out.println("=============================================");

}

}

public class mainClass extends Object {

public static void main (String[] param)
{
parseString parse =new parseString();
parse.findRepeat("CATAAABBBAAA");

}
}

Hi as suggested above i am trying to use the knuth-morris-pratt algorithm and have coded this program
though it compiles i am not geting an output could any boby help me make this functional
the parse method creates all subset of the string input
the Match function matches the patern with the string and keeps a count if the string matches
calls buildLastFunction to convert to Ascii can anybody tell me why this is not working ,help me fix it for the problem above


import java.util.*;
import java.lang.*;
class codeJava{
LinkedList l = new LinkedList();
void Parse(String s)
{

String a = s.toLowerCase();
String b = null;
int n=a.length();
int count = 0;
for ( int i=0; i <= n; i++){
for ( int k=0 ; k<=n ; k++){
try{
b = a.substring(i,k);
l.add(b);
Match(a,l.get(i).toString());

}

catch(Exception e){

}

}
}
Iterator m=l.iterator();


}

public int[] buildLastFunction(String pattern){
int[] last=new int[128];//assume ASCII CHARACTER SET
for(int i=0;i<128;i++){
last[i]=-1;//initialize array
for(i=0;i< pattern.length();i++){
last[pattern.charAt(i)] = i;//IMPLICIT cast to integer ASCII

}
}
return last;
}
public int Match(String text,String pattern){
int[]last = buildLastFunction(pattern);
TreeSet d=new TreeSet();
int n = text.length();
int m = pattern.length();
int i = m-1;
if(i>n-1){
System.out.println("the pattern is longer than the text");
return -1;}//no match if pattern is longer than text
int j=m-1;
int count=0;


do{
if(pattern.charAt(j)==text.charAt(i))
{
if(j==0)
{
count=count+1;//match
if(count > 1 )
{
d.add(l.get(i) +" "+count);
}
count=0;
if (!d.isEmpty()){
System.out.println("the patterns are");
System.out.println(d);
}
}else{ //left-right scan
i--;j--; count=0;

}
}
else
{
i+=m - Math.min(j, 1+ last[text.charAt(i)]);//bad character huristics
j = m-1;
}
}while(i<=n-1);
return -1;
//no match

}
public static void main (String[] param)
{
codeJava find =new codeJava();
find.Parse("cattocat");

}
}


Thanks

let me rephrase the question as
how can we find the largest repeatingg substring in a given string and displaying the number of times it has repeated
can any body tell me the logic with the code any language

hi, here is a way to do it in java...I left some things unimplemented, so you will still have to figure stuff out. I think this will do what you want, if not, I hope it helps out some.

main()
{
int maxRepeat=0;
String patternRepeated="";//these 2 values are to store the
// most repeated pattern

inputString-assign the string to a variable
int size=inputString.length(); //store this for use in next loop

//loop through the string checking different lengths
//starting with length 2 and going up to size/2
//only loop to size/2....because if its half the size of
// the entire string, it can only repeat once anyway

//this loop specifies the length of the current pattern being checked
for(int i=2;i<(size/2);i++)
{
//next loop checks the string for all patterns of size i
for(int j=0;j<size-i;j++) // may need to be (size-(i+1))
{ String temp=inputString.substring(j,j+i);
int current=checkRepeat(temp,inputString);
// if the current pattern was repeated more, save it
// and continue looping
if(current>maxRepeat)
{ maxRepeat=current;
patternRepeated=new String(temp);
}
}
}
System.out.println("pattern repeated most: "+patternRepeated);
System.out.println("num of times repeated: "+maxRepeat);
}

int checkRepeat(String temp, String inputString)
{ int count=0;
//next loop runs through the original string(inputString) and
// looks for the temp string(pattern)...it increments count if
// the pattern was found
//may need to be (inputString.length()-(1+temp.length()))
for(int i=0;i<inputString.length()-temp.length();i++)
if( inputString.substring(i,i+temp.length()).compareTo(temp)==0 )
count++;
return count;
}