IndexOf Implementation :-
public static int[] FailureFunction(string p)
{
int[] F = new int[p.Length];
F[0] = 0;
int i = 1, j = 0;
while (i < F.Length)
{
if (p[i] == p[j])
{
F[i] = j + 1;
i++;
j++;
}
else if (j > 0)
{
j = F[j - 1];
}
else
{
F[i] = 0;
j++;
}
}
return F;
}
public static int KMP(string s, string p)
{
int[] F = FailureFunction(p);
int i = 0, j = 0;
while (i < s.Length)
{
if (s[i] == p[j])
{
if (j == p.Length-1)
{
return i - j;//match
}
else
{
i++; j++;
}
}
else
{
if (j > 0)
{
j = F[j - 1];
}
else
{
i++;
}
}
}
return -1;
}
public static int[] FailureFunction(string p)
{
int[] F = new int[p.Length];
F[0] = 0;
int i = 1, j = 0;
while (i < F.Length)
{
if (p[i] == p[j])
{
F[i] = j + 1;
i++;
j++;
}
else if (j > 0)
{
j = F[j - 1];
}
else
{
F[i] = 0;
j++;
}
}
return F;
}
public static int KMP(string s, string p)
{
int[] F = FailureFunction(p);
int i = 0, j = 0;
while (i < s.Length)
{
if (s[i] == p[j])
{
if (j == p.Length-1)
{
return i - j;//match
}
else
{
i++; j++;
}
}
else
{
if (j > 0)
{
j = F[j - 1];
}
else
{
i++;
}
}
}
return -1;
}
No comments:
Post a Comment