Biegral Blog

using System;
using System.Text;
using System.IO;
namespace KMP
{
    class Kmp
    {
        public int[] next;
        public string mainStr;//主串  
        public string modeStr;//模式串  
        public Kmp(string ms)
        {
            next = new int[ms.Length];
            next[0] = -1;
            next[1] = 0;
        }
        public void GetNext()  //获取模式串的next数组  
        {
            for (int j = 2; j < modeStr.Length; j++)
            {
                next[j] = 0;
                for (int k = 1; k < j; k++)
                {
                    string s1 = "";
                    string s2 = "";
                    for (int i = 0; i <= k; i++)
                    {
                        s1 += modeStr[i];
                        s2 += modeStr[j - k];
                        if (s1 == s2)
                        {
                            next[j] = next[j] > k ? next[j] : k;
                        }
                    }
                }
            }
        }
        public void GetNextval()  //改进的kmp算法，即修改next  
        {
            for (int i = 2; i < next.Length; i++)
            {
                while (true)
                {
                    if (next[i] != -1 && modeStr[i] == modeStr[next[i]])
                    {
                        next[i] = next[next[i]];
                    }
                    else
                    {
                        break;
                    }
                }
            }
        }
    }
    class Program
    {
        static void Main()
        {
            string mainPath = @"F://test.txt";  //主串所在文件  
            string modePath = @"F://test1.txt"; //模式串所在文件  
            StreamReader sr = new StreamReader(mainPath, Encoding.Default);
            string mainSt = ""; //用来存放主串  
            string s;
            while ((s = sr.ReadLine()) != null)
            {
                mainSt += s;
            }
            sr = new StreamReader(modePath, Encoding.Default);
            string modeStr = "";  //用来存放模式串  
            while ((s = sr.ReadLine()) != null)
            {
                modeStr += s;
            }
            Kmp kmp = new Kmp(modeStr);  //创建一个kmp对象  
            kmp.modeStr = modeStr;   //将读取到的模式串副歌相应的变量  
            kmp.mainStr = mainSt;
            kmp.GetNext();   //获取模式串的next内容  
            kmp.GetNextval();//修改next的内容
            for (int i = 0; i < kmp.next.Length; i++) 
            { 
                Console.WriteLine(kmp.next[i]); 
            }
            for (int i = 0, j = 0; i < modeStr.Length && j < mainSt.Length; j++)
            {
                if (modeStr[i] == mainSt[j])  //判断两个字符是否相等  
                {
                    if (i == modeStr.Length - 1)  //模式串的最后一个字符匹配成功  
                    {
                        Console.WriteLine("在{0}处匹配成功", j - modeStr.Length);
                        break;
                    }
                    i++;
                    continue;
                }
                else if (j == mainSt.Length - 1)  //已经到达主串的最后一个字符  
                {
                    Console.WriteLine("匹配失败");
                }
                else if (kmp.next[i] == -1)
                {
                    i = kmp.next[i] + 1; //i=next[i]=-1修改为i=i+1=0;  
                }
                else
                {
                    i = kmp.next[i];
                }
            }
        }
    }
}