wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Repeated String
        
(Message started by: johny_cage on Nov 24^th, 2007, 5:58am)

Title: Repeated String
Post by johny_cage on Nov 24^th, 2007, 5:58am

Find the first 4 character substring in a given string that occurs more than once. and return its starting index. E.g. for “abcdebcxbcdebyz” output should be “bcde” and index is 1.

Title: Re: Repeated String
Post by towr on Nov 24^th, 2007, 6:12am

Seems like a duplicate of the thread Finding "Substring Position" (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1194851194).
Even the example used is the same, although Robin posed the question more generally.

Title: Re: Repeated String
Post by downloadprj on Nov 24^th, 2007, 7:11am

Following code finds the repeating substring of size 4 or less in the input string.

int Substr(char str[], char sub[], int subSize)
{
for (int i = 0; str[i] != '\0'; i++)
{
for (int j = 0, k = i; (str[k] == sub[j]) && (j < subSize); j++, k++);
if (j == subSize)
return 1;
}

return 0;
}

int LongestRepeatingSubString(char str[])
{
int length = 4;
for (int sublen = length/2; sublen != 1; sublen--)
{
for (int i = 0; i + sublen <= length - sublen; i++)
{
if (Substr(str + sublen + i, str + i, sublen) == 1)
{
char t = str[i + sublen];
str[i + sublen] = '\0';
printf("%s\n", str + i);
str[i + sublen] = t;
return sublen;
}
}
}
}