数据结构04 串的朴素匹配

在串的问题里，匹配是很重要的一类问题。匹配是在一个给定的主串中寻找一个相同的子串，确定子串出现的位置。

一个朴素的做法是，将主串和子串逐字符比较。用指针移动两字符。步骤如下：

1: 有两指针，其中一个i指向主串查找的位置，另外j一个指针指向子串的首位。

2: 比较两指针所指的字符。如果相同，两指针都移动一位。如果不同，j回到子串首位，i回到比较的初始位置+1位。

3: 直至j大于子串的长度。说明找到一个匹配的位置。

以下是找出一个主串的所有匹配子串位置的c语言代码。

int Index(str S,str T,int pos)
{
  int i,j;
  i = pos - 1;
  while(i < strlen(S))
  {
    j = 0;
     while(i < strlen(S) && j < strlen(T))
    {
      if (S[i] == T[j])
      {
        ++i;
        ++j;
      }
      else
      {
        i = i - j + 1;
        j = 0;
      }
    }
    if (j >= strlen(T))
    {
        // K = i - strlen(T) + 1;
        printf("The word is at %lu
",i - strlen(T) + 1);
        // return 0;
    }
  }
  return 0;
}

以下是找出一个主串的所有匹配子串位置的python语言代码。

class index(object):
    def __init__(self,s,t,pos):
        self.s = s
        self.t = t
        self.pos = pos
    def index(self):
        i = self.pos - 1;
        while i < len(self.s):
            j = 0
            while j < len(self.t) and i < len(self.s):
                if self.s[i] == self.t[j]:
                    i = i + 1
                    j = j + 1
                #if
                else:
                    i = i - j + 1
                    j = 0
                #else
            #while
            if j >= len(self.t):
                print ("The word is at:%d" % (i - len(self.t) + 1) )

（完）

下一篇介绍KMP算法的理解。

数据结构04 串的朴素匹配

相关推荐