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