C#，字符串匹配算法（模式搜索）Z算法的源代码与数据可视化

Z算法也是模式搜索（Pattern Search Algorithm）的常用算法。

本文代码的运算效果：

一、Z 算法

线性时间模式搜索算法的Z算法，在线性时间内查找文本中模式的所有出现。

假设文本长度为 n，模式长度为 m，那么所用的总时间为 O(m + n)，空间复杂度为线性。现在我们可以看到时间和空间复杂度都和 KMP 算法一样，但是这个算法更容易理解。

在这个算法中，我们构造了一个 Z 数组。

什么是 Z 数组？ 为字符串[0..n-1]，Z 数组与字符串长度相同。Z 数组的元素 Z[i]存储从字符串[i]开始的最长子串的长度，字符串[i]也是字符串[0]的前缀..n-1]。Z 数组的第一个条目意义不大，因为完整的字符串总是它自己的前缀。

二、核心代码

#define ANIMATE
using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Algorithm.PatternSearch
{
    /// <summary>
    /// Z算法模式搜索
    /// </summary>
    public class Z_Algorithm
    {
#if ANIMATE
        public List<string> slides { get; set; } = new List<string>();
        private string[] stringArray { get; set; } = null;
#endif

        /// <summary>
        /// 构建Z数组并进行Z算法模式搜索
        /// </summary>
        /// <param name="text"></param>
        /// <param name="pattern"></param>
        /// <returns></returns>
        public string Search(string text, string pattern)
        {
            // 构造模式字串与原始字符串的合并串 "P$T"
            string concat = pattern + "$" + text;
            // 以合并串构建Z数组
            int[] Z = Z_Array_Build(concat);

            for (int i = 0; i < concat.Length; i++)
            {
#if ANIMATE
                slides.Add(ToHtml(Z, i));
#endif

                if (Z[i] == pattern.Length)
                {
                    return "模式位于：" + (i - pattern.Length - 1);
                }
            }

            return "未找到匹配模式！";
        }

        /// <summary>
        /// 依据 字符串构建 Z 数组
        /// </summary>
        /// <param name="str"></param>
        private int[] Z_Array_Build(string str)
        {
            int n = str.Length;
            int[] Z = new int[n];
            int L = 0;
            int R = 0;
#if ANIMATE
            stringArray = new string[n];
            stringArray[0] = str.Substring(0, 1);
#endif
            for (int i = 1; i < n; i++)
            {
#if ANIMATE
                stringArray[i] = str.Substring(i, 1);
#endif
                if (i > R)
                {
                    L = R = i;
                    while (R < n && str[R - L] == str[R])
                    {
                        R++;
                    }
                    Z[i] = R - L;
                    R--;
                }
                else
                {
                    int k = i - L;
                    if (Z[k] < R - i + 1)
                    {
                        Z[i] = Z[k];
                    }
                    else
                    {
                        L = i;
                        while (R < n && str[R - L] == str[R])
                        {
                            R++;
                        }
                        Z[i] = R - L;
                        R--;
                    }
                }
            }

            return Z;
        }
#if ANIMATE
        private string ToHtml(int[] Z, int index)
        {
            StringBuilder sb = new StringBuilder();
            sb.Append("<style>td { padding:5px;text-align:center; }</style>");
            sb.Append("<table border=1 style='border-collapse:collapse;'>");
            sb.Append("<tr>");
            sb.Append("<td>string</td>");
            for (int i = 0; i < stringArray.Length; i++)
            {
                sb.Append("<td>" + stringArray[i] + "</td>");
            }
            sb.Append("</tr>");
            sb.Append("<tr>");
            sb.Append("<td>z array</td>");
            for (int i = 0; i < Z.Length; i++)
            {
                if (i == index)
                {
                    sb.Append("<td style='background-color:#FF6701;color:#FFFFFF;'>" + Z[i] + "</td>");
                }
                else
                {
                    sb.Append("<td style='background-color:#FFDD99;'>" + Z[i] + "</td>");
                }
            }
            sb.Append("</tr>");
            sb.Append("</table>");
            return sb.ToString();
        }
#endif
    }
}

三、数据可视化代码

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

using Legalsoft.Algorithm.PatternSearch;

namespace WindowsFormsApp1
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        private void Form1_Load(object sender, EventArgs e)
        {
            this.Text = "C#，模式搜索Z算法（线性时间模式搜索算法）——北京联高软件开发有限公司";
            button1.Text = "Z算法"; button1.Cursor = Cursors.Hand;
            panel1.Dock = DockStyle.Top;
            panel2.Dock = DockStyle.Fill;
            webBrowser1.Navigate("http://www.315soft.com");

            textBox1.Text = "C#，模式搜索Z算法（线性时间模式搜索算法）,联高软件";
            textBox2.Text = "Z算法";
        }

        private void button1_Click(object sender, EventArgs e)
        {
            Z_Algorithm z = new Z_Algorithm();
            z.Search(textBox1.Text.Trim(), textBox2.Text.Trim());
            slides.AddRange(z.slides);

            loop = 0;
            timer1.Interval = 1000;
            timer1.Enabled = true;
        }

        int loop = 0;
        List<string> slides = new List<string>();

        private void timer1_Tick(object sender, EventArgs e)
        {
            if (loop < slides.Count + (3000 / timer1.Interval))
            {
                if (loop < slides.Count)
                {
                    StringBuilder sb = new StringBuilder();
                    sb.AppendLine("<style>* { font-size:21px; } </style>");
                    sb.AppendLine("Source String: <font color=red>" + textBox1.Text.Trim() + "</font><br>");
                    sb.AppendLine("Pattern String: <font color=blue>" + textBox2.Text.Trim() + "</font><br>");
                    sb.AppendLine("<br>");
                    sb.Append(slides[loop]);
                    webBrowser1.DocumentText = sb.ToString();
                    loop++;
                    return;
                }
                loop++;
                return;
            }
            loop = 0;
        }

    }
}
 

---------------------------------------------
POWER BY TRUFFER.CN