串的两种模式匹配算法
  模式匹配(模范匹配)：⼦串在主串中的定位称为模式匹配或串匹配(字符串匹配) 。模式匹配成功是指在主串S中能够到模式串T，否则，称模式串T在主串S中不存在。
  以下介绍两种常见的模式匹配算法：
1. Brute-Force模式匹配算法暴风算法，⼜称暴⼒算法。
  算法的核⼼思想如下：
  设S为⽬标串，T为模式串，且不妨设：
  S=“s0s1s2…sn-1” ， T=“t0t1t2 …tm-1”
  串的匹配实际上是对合法的位置0≦i≦n-m依次将⽬标串中的⼦串s[i…i+m-1]和模式串t[0…m-1]进⾏⽐较：
若s[i…i+m-1]=t[0…m-1]：则称从位置i开始的匹配成功，亦称模式t在⽬标s中出现；
若s[i…i+m-1]≠t[0…m-1]：从i开始的匹配失败。位置i称为位移，当s[i…i+m-1]=t[0…m-1]时，i称为有效位移；当s[i…i+m-1] ≠t[0…m-1]时，i称为⽆效位移。
  算法实现如下：
  （笔者偷懒，⽤C#实现，实际上C# String类型已经封装实现了该功能）
1public static Int32 IndexOf(String parentStr, String childStr)
2        {
3            Int32 result = -1;
4try
5            {
6if (parentStr.Length > 1 && childStr.Length > 1)
7                {
8                    Int32 i = 0;
9                    Int32 j = 0;
10while (i < parentStr.Length && j < childStr.Length)
11                    {
12if (parentStr[i] == childStr[j])
13                        {
14                            i++;
15                            j++;
16                        }
17else
18                        {
19                            i = i - j + 1;
20                            j = 0;
字符串长度17模式串长度821                        }
22                    }
23if (i < parentStr.Length)
24                    {
25                        result = i - j;
26                    }
27                }
28            }
29catch (Exception)
30            {
31                result = -1;
32            }
33return result;
34        }
  该算法的时间复杂度为O(n*m) ，其中n 、m分别是主串和模式串的长度。
  2.KMP算法，该算法是对上述暴风算法的⼀种改进实现算法，其改进之处在于：
  每当⼀趟匹配过程出现字符不相等时，主串指⽰器不⽤回溯，⽽是利⽤已经得到的“部分匹配”结果，将模式串的指⽰器向右“滑动”尽可能远的⼀段距离后，继续进⾏⽐较。核⼼思想：“利⽤已经部分匹配这个有效信息，保持i指针不回溯，通过修改j指针，让模式串尽量地移动到有效的位置。”

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。