KMP字符串匹配算法

 

 

static void Main(string[] args)
{
var d = KMP("abcabcadabc55abcabcadabc55", "abcabcadabc");
}
static List<int> KMP(string s, string p)
{
int[] pi = ComputePrefix(p);
    List<int> result = new List<int>();
int q = 0;
for (int i = 0; i < s.Length; i++)
    {
//如果不相等了，查看这次匹配不相等的下次匹配个数
while (q > 0 && p[q] != s[i])
            q = pi[q - 1];
//记录已经相等的个数
if (p[q] == s[i])
            q++;
if (q == p.Length - 1)
        {
            result.Add(i - q);
            q = pi[q - 1] + 1;
        }
    }
return result;
}
static int[] ComputePrefix(string p)
{
var pi = new int[p.Length];
    pi[0] = 0;
int k = 0;
for (int i = 1; i < p.Length; i++)
    {
//如果不相等了，查看这次匹配不相等的下次匹配个数
while (k > 0 && p[k] != p[i])
            k = pi[k - 1];
//记录已经相等的个数
if (p[k] == p[i])
            k++;
        pi[i] = k;
    }
return pi;
}