billu
BAN USERSuggesting approach here which is easy to code
1. Get length of both the strings.
2. If length are same then, keep two pointers and traverse both the string, if characters match forward them, if characters dont match and its for very first time, move on. If you reach at the end, declare true if you find more than 1 mismatch return false for the 2nd mismatch.
3. If the length difference between two string is exactly 1(it means we can get either of the string by Insert/delete of one character), do the same but for the very fist mismatch, ignore the character in longer string and increment the longer string pointer and compare, if you reach at the end, return TRUE or for any further mismatch, return false.
I am trying to author your algorithm using non resursive solution, however its failing for below two cases, Can you suggest why ?
assert(FindSubArray!('#','*')("###****") == "###***");
assert(FindSubArray!('#','*')("#*#*#****") == "#*#*#*");
private static void findlongestseq()
{
//char[] str = "**###***#**##*###*#*".ToCharArray();
char[] str = "###****".ToCharArray();
int[] b = new int[str.Length];
int i = 0;
while (i < str.Length)
{
char c = str[i];
int count = 0;
int index = i;
while (index<str.Length && c == str[index] )
{
count++;
index++;
}
bool isFirst = true;
index=i;
while (count >= 1)
{
if (isFirst)
{
b[index] = count;
isFirst = false;
}
else
{
b[index] = 0;
}
count--;
index++;
}
i = index;
}
i=0;
int j = 0;
int maxfound = -1;
int starterindex = 0;
while (i < str.Length)
{
while (i < str.Length && b[i] == 0)
{
i++;
}
j=i+1;
while(j< str.Length && b[j] == 0)
{
j++;
}
if (i < str.Length && j < str.Length)
{
if (b[i] == b[j])
{
if (b[i] > maxfound)
{
maxfound = b[i];
starterindex = i;
}
}
}
j = i;
i++;
}
if (maxfound != -1)
{
Console.WriteLine("Longest string found is ");
int counter = maxfound * 2;
while ( counter> 0)
{
Console.Write(str[starterindex]);
starterindex++;
counter--;
}
}
else
{
Console.WriteLine("NOP");
}
}
- billu July 15, 2015