首页 > 代码库 > KMP算法 C#简单实现
KMP算法 C#简单实现
KMP算法 C#简单实现
最近在学习数据结构，将KMP算法用C#简单实现了下。
static void Main(string[] args)
{char[] source = {‘b‘,‘b‘,‘c‘,‘ ‘,‘a‘,‘b‘,‘c‘,‘d‘,‘a‘,‘b‘,‘a‘,‘b‘,‘c‘,‘d‘,‘a‘,‘b‘,‘a‘,‘b‘,‘c‘,‘d‘,‘a‘,‘b‘,‘a‘,‘b‘,‘c‘,‘d‘,‘a‘,‘b‘,‘a‘,‘b‘,‘c‘,‘d‘,‘a‘,‘b‘,‘a‘,‘b‘,‘c‘,‘d‘,‘a‘,‘b‘,‘a‘,‘b‘,‘c‘,‘d‘,‘a‘,‘b‘,‘a‘,‘b‘,‘c‘,‘d‘,‘a‘,‘b‘,‘a‘,‘b‘,‘c‘,‘d‘,‘a‘,‘b‘,‘a‘,‘b‘,‘c‘,‘d‘,‘a‘,‘b‘,‘a‘,‘b‘,‘c‘,‘d‘,‘ ‘,‘a‘,‘b‘,‘c‘,‘d‘,‘a‘,‘b‘,‘c‘,‘d‘,‘a‘,‘b‘,‘d‘,‘e‘};
char[] target = {‘a‘,‘b‘,‘c‘,‘d‘,‘a‘,‘b‘,‘d‘};
int index = getStartIndex(source, target);
Console.WriteLine("匹配开始位置为："+index);
}
static int getStartIndex(char[] s, char[] t)
{
int time = 0;//统计计算的次数
int[] next = initNext(t);
int i = 0, j = 0;
for ( i = 0; i < s.Length; )
{
for ( j = 0; j < t.Length;)
{
time++;
if (s[i] == t[j])
{
i++;
j++;
}
else
{
i = j>0?i - next[j-1]:i+1;
break;
}
}
if (j == t.Length)
return i-t.Length;
}
return -1;
}
static int[] initNext(char[] t)
{
int[] ret = new int[t.Length];
for(int i=0;i<t.Length;i++)
ret[i]=0;
for (int i = 1; i < t.Length; i++)
{
int temp = 0;
for (int j = 0; j < t.Length; j++)
{
while (t[i] == t[j] && i < t.Length && j < t.Length)
{
ret[i] = ++temp;
i++;
j++;
}
break;
}
}
return ret;
}
KMP算法 C#简单实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。