KMP算法代码,C#代码库,德仔网

代码语言

代码分类

【C#】 KMP算法

作者:april / 发布于2016/9/9/ 691

static void BuildTable(string subString, ref int[] next)
{
    if (string.IsNullOrWhiteSpace(subString)) return;
 
    int j = 0, k = -1;
    next[0] = -1;
    while (j < subString.Length - 1)
    {
        if (-1 == k || subString[j] == subString[k])
        {
            j++;
            k++;
            next[j] = k;
        }
        else
        {
            k = next[k];
        }
    }
}
 
/// <summary>
/// 查找算法
/// </summary>
/// <param name="source">要搜索的字符串</param>
/// <param name="subString">子串</param>
/// <returns>子串在source字符串中的开始位置</returns>
static int KmpSearch(string source, string subString)
{
    if (string.IsNullOrWhiteSpace(source) || string.IsNullOrWhiteSpace(subString))
        return -1;
    var next = new int[subString.Length];
    for (int k = 0; k < next.Length; k++)
    {
        next[k] = -1;
    }
    int i = 0, j = 0,sLen = subString.Length;
 
    BuildTable(subString, ref next);
 
    while (i < sLen)
    {
        if (j == -1 || source[i] == subString[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
 
        if (j == sLen)
        {
            return i - sLen;
        }
    }
    return -1;
}
使用

1
2
3
4
5
6
string source = "我是中和敏式的服务二是到覅维尔维尔34山东富翁234斯蒂芬234234式的服务二";
string subString = "山东富翁";
 
int a = KmpSearch(source, subString);
 
Console.WriteLine(a);

试试其它关键字

　KMP算法　

同语言下

可能有用的

april贡献的其它代码(15)