leeyupeng

leeyupeng@126.com

0%

KMP算法

发表于 更新于 分类于 ， 阅读次数： Valine：

KMP算法

next函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void GetNext(char* p,int next[])  
{  
    int pLen = strlen(p);  
    next[0] = -1;  
    int k = -1;  
    int j = 0;  
    while (j < pLen - 1)  
    {  
        //p[k]表示前缀，p[j]表示后缀  
        if (k == -1 || p[j] == p[k])   
        {  
            ++k;  
            ++j;  
            next[j] = k;  
        }  
        else   
        {  
            k = next[k];  
        }  
    }  
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//优化过后的next 数组求法  
void GetNextval(char* p, int next[])  
{  
    int pLen = strlen(p);  
    next[0] = -1;  
    int k = -1;  
    int j = 0;  
    while (j < pLen - 1)  
    {  
        //p[k]表示前缀，p[j]表示后缀    
        if (k == -1 || p[j] == p[k])  
        {  
            ++j;  
            ++k;  
            //较之前next数组求法，改动在下面4行  
            if (p[j] != p[k])  
                next[j] = k;   //之前只有这一行  
            else  
                //因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]  
                next[j] = next[k];  
        }  
        else  
        {  
            k = next[k];  
        }  
    }  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int KmpSearch(char* s, char* p)  
{  
    int i = 0;  
    int j = 0;  
    int sLen = strlen(s);  
    int pLen = strlen(p);  
    while (i < sLen && j < pLen)  
    {  
        //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++      
        if (j == -1 || s[i] == p[j])  
        {  
            i++;  
            j++;  
        }  
        else  
        {  
            //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]      
            //next[j]即为j所对应的next值        
            j = next[j];  
        }  
    }  
    if (j == pLen)  
        return i - j;  
    else  
        return -1;  
}

正则表达式 模式匹配 静态KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
vector<int> GetNextval(string p)
{
  int pLen = p.length();
  vector<int> next(pLen, 0);
  next[0] = -1;
  int k = -1;
  int j = 0;

  while (j < pLen - 1)
  {
    if (p[j] == '*')
    {
      k = j;
      ++j;
      next[j] = k;
    }
    else if (k == -1 || (p[j] == p[k] || p[j] == '?' || p[k] == '?' || p[j] == '*' || p[k] == '*'))
    {
      ++j;
      ++k;
      if (p[j] != p[k] || p[j] == '?' || p[k] == '?' || p[j] == '*' || p[k] == '*')
      {
        next[j] = k;
      }
      else
      {
        if (k != 0 && p[k - 1] == '*')
        {
          next[j] = k - 1;
        }
        else
        {
          next[j] = next[k];
        }
      }
    }
    else
    {
      k = next[k];
    }
  }
  return next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
bool isMatch(string s, string p) {
  if (p.empty())
  {
    if (s.empty())
    {
      return true;
    }
    else
    {
      return false;
    }
  }
  string pp =p;
  pp.push_back('?');
  vector<int> next = GetNextval(pp);

  int i = 0;
  int j = 0;
  int k = 0;
  int kk = 0;
  int sLen = s.length();
  int pLen = p.length();

  bool starFlag = false;
  while (i < sLen)
  {
    if (j == -1)
    {
      break;
    }

    while (j < pLen && p[j] == '*')
    {
      starFlag = true;
      j++;
    }

    if (j < pLen && (s[i] == p[j] || p[j] == '?' || p[j] == '*'))
    {
      i++;
      j++;
    }
    else
    {   
      if (starFlag == false)
      {
        break;
      }

      //j = next[j];

      //验证?
      k = next[j];
      while (k > 0)
      {						
        kk = k;
        while (kk >= 0 && p[kk] != '*')
        {
          if (p[j - (k - kk)] == '?' && p[kk] != '?')
          {
            if (s[i - (k - kk)] != p[kk])
            {
              break;
            }
          }
          kk--;
        }
        if (kk < 0 || p[kk] == '*')
        {
          break;
        }
        else
        {
          k = next[k];
        }
      }

      j = k;

      if (p[j] == '*')
      {
        i++;
      }
    }
  }

  while (j < pLen && p[j] == '*')
  {
    j++;
  }
  if (i == sLen && j == pLen)
    return true;
  else
    return false;
}

参考

- KMP算法