|
ALongest substring repeated multiple number of times.
Microsoft Interview Questions and Answers
(Continued from previous question...)
105. ALongest substring repeated multiple number of times.
Question:
Longest substring repeated multiple number of times.
maybe an answer:
#include <iostream>
using namespace std;
int getNext(char * str, int leng, int * next)
{
if (leng < 0 || str == NULL)
return -1;
int i = 0, j = -1, max = 0;
next[0] = -1;
while (i < leng)
if (j == -1 || str[i] == str[j])
{
++i; ++j;next[i] = j;
//////////////// My code.
if (next[i] > max)
max = next[i];
//////////////////All other parts of this method is from KMP
}
else
j = next[j];
return max;
}
//Utilize the getNext method to find the length of the longest repeated substring.
int getMaxRepeat(char * s, int leng)
{
int * next = new int[leng];
int max = 0;
for (int i = 0; i < leng; ++i)
{
int cur_max = getNext(s+i, leng - i, next);
if (cur_max > max)
max = cur_max;
}
delete [] next;
return max;
}
int main()
{
char * s = "xxxabababab";
int leng = strlen(s);
cout<
getchar();
}
(Continued on next question...)
Other Interview Questions
| 