leeyupeng

leeyupeng@126.com

0%

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

0/1背包问题

题目

- 3624.Charm Bracelet

描述

有N个物品，每个物品的价值di和重量wi，背包容量为M，每个物品最多可以装入背包一个，求背包可以装的物品的总价值

公式

dp[j] = dp[j] > dp[j - v[i].weight] + v[i].desirability
? dp[j] : dp[j - v[i].weight] + v[i].desirability;

动态规划

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
#include <iostream>
#include <vector>
using namespace std;

struct charm
{
	int weight;
	int desirability;
};
int CharmBracelet(vector<charm>& v, int n, int m)
{
	vector<int> dp(m + 1);
	dp[0] = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = m; j >= v[i].weight; j--)
		{
			dp[j] = dp[j] > dp[j - v[i].weight] + v[i].desirability
				? dp[j] : dp[j - v[i].weight] + v[i].desirability;
		}
	}
	return dp[m];
}

int main()
{
	int n, m;
	cin >> n >> m;
	vector<charm> v(n);
	for (int i = 0; i < n; i++)
	{
		cin >> v[i].weight;
		cin >> v[i].desirability;
	}

	int result = CharmBracelet(v, n, m);
	cout << result << endl;
	return 0;
}
阅读全文 »

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

0/1背包问题

题目

- 3624.Charm Bracelet

描述

有N个物品，每个物品的价值di和重量wi，背包容量为M，每个物品最多可以装入背包一个，求背包可以装的物品的总价值

剪枝

1.w==0
2.if ((ans - d)(v)[index].weight >= w (v)[index].desirability),使用粗略剪枝会超时，不靠谱
3.index w d 下一直往背包装，能够取得的最大值和当前的ans比较大小，小于当前ans 剪枝

回溯法DFS

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
96
97
98
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct charm
{
	int weight;
	int desirability;
};

vector<charm>* v = NULL;
int ans = 0;
void dfs(int index,int w,int d)
{
	if (index < 0)
	{
		ans = ans > d ? ans : d;
		return;
	}

	//剪枝
	if (w == 0)
	{
		ans = ans > d ? ans : d;
		return;
	}

	//剪枝
	//if ((ans - d)*(*v)[index].weight >= w * (*v)[index].desirability)
	//{
	//	return;
	//}

	//剪枝
	if(ans > d)
	{
		int anstemp = d;
		int wtemp = w;
		int indextemp = index;
		while (indextemp >= 0 && wtemp >= (*v)[indextemp].weight)
		{
			anstemp += (*v)[indextemp].desirability;
			wtemp -= (*v)[indextemp].weight;
			indextemp--;
		}
		if (indextemp >= 0)
		{
			anstemp += wtemp * (*v)[indextemp].desirability / (*v)[indextemp].weight;
		}
		if (ans >= anstemp)
		{
			return;
		}
	}

	if ((*v)[index].weight <= w)
	{
		dfs(index - 1, w - (*v)[index].weight, d + (*v)[index].desirability);
	}

	dfs(index - 1, w, d);
}
bool cmp(charm c1, charm c2)
{
	if (c1.desirability * c2.weight == c2.desirability * c1.weight)
	{
		return c1.weight < c2.weight;
	}
	else
	{
		return 1.0f * c1.desirability / c1.weight < 1.0f * c2.desirability / c2.weight;
	}
}
int CharmBracelet(vector<charm>* v, int n, int m)
{
	sort(v->begin(), v->end(), cmp);

	dfs(n-1,m,0);

	return ans;
}
int main()
{
	int n, m;
	cin >> n >> m;
	v = new vector<charm>(n);
	for (int i = 0; i < n; i++)
	{
		cin >> (*v)[i].weight;
		cin >> (*v)[i].desirability;
	}
	int result = CharmBracelet(v, n, m);
	delete v;
	v = NULL;
	cout << result << endl;
	return 0;
}
阅读全文 »

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

Subset

题目

3977.Subset

描述

Given a list of N integers with absolute values no larger than 1015, find a non empty subset of these numbers which minimizes the absolute value of the sum of its elements. In case there are multiple subsets, choose the one with fewer elements.
The input contains multiple data sets, the first line of each data set contains N <= 35, the number of elements, the next line contains N numbers no larger than 1015 in absolute value and separated by a single space. The input is terminated with N = 0
For each data set in the input print two integers, the minimum absolute sum and the number of elements in the optimal subset.

—-

subset sum problem 子集和问题
有N个数，可能为负数，[- 10的15次方,10的15次方之间]，求子集和中 绝对值最小的子集

折半搜索

阅读全文 »

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

零钱兑换

322.零钱兑换

公式

dp[i] = Math.min(dp[i], dp[i - coin] + 1)

代码

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
class Solution {
public:
  int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1);

    dp[0] = 0;
    for (int n = 1; n <= amount; n++)
    {
      dp[n] = -1;
      for (int i = 0; i < coins.size(); i++)
      {
        if (n - coins[i] >= 0 && dp[n - coins[i]] != -1)
        {
          if (dp[n] == -1)
          {
            dp[n] = dp[n - coins[i]] + 1;
          }
          else if (dp[n] > dp[n - coins[i]] + 1)
          {
            dp[n] = dp[n - coins[i]] + 1;
          }
        }
      }
    }

    return dp[amount];
  }
};
阅读全文 »

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

计算器

题目

- leetcode 224. 基本计算器

递归

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
class Solution {
public:

	//词素
	struct morpheme
	{
		long digital;
		char ops;
		int type;
		int priority = -1;

		morpheme(int t, int d, char o, int p)
		{
			type = t;
			digital = d;
			ops = o;
			priority = p;
		}

		morpheme()
		{
		}
	};

	string skipspace(string s)
	{
		string ans;

		for (int i = 0; i < s.size(); i++) {
			char c = s[i];
			if (c != ' ') {
				ans.push_back(c);
			}
		}
		return ans;
	}
	void scanning(const string str, vector<morpheme>& v)
	{
		char morphemetype[] = { ')','+','-','*','/','(' };
		int morphemetypelength = 6;

		long digit = 0;
		int len = str.length();
		for (int i = 0; i < len; i++)
		{
			char c = str[i];
			if (c == ' ')
			{
				continue;
			}
			bool flag = false;
			for (int j = 0; j < morphemetypelength; j++)
			{
				if (c == morphemetype[j])
				{
					v.push_back(morpheme(j, 0, c, j));
					flag = true;
				}
			}

			if (flag == false)
			{
				digit = digit * 10 + (int)c - 0x30;

				if (i == len - 1 || (str[i + 1] < '0' || str[i + 1] > '9'))
				{
					v.push_back(morpheme(-1, digit, '\0', -1));
					digit = 0;
				}
			}
		}
	}
	int recursive(vector<morpheme>& out,vector<morpheme>& in,int left,int right)
	{
		for (int i = left; i < right; )
		{
			if (in[i].type == 5)
			{
				vector<morpheme> outtemp2;
				int bracketright = recursive(outtemp2,in, i + 1,right);
				for (int j = 0; j < outtemp2.size(); j++)
				{
					out.push_back(outtemp2[j]);
				}
				i= bracketright + 1;
			}
			else if (in[i].type == 0)
			{
				long value = calculator(out, 0, out.size());
				out.clear();
				out.push_back(morpheme(-1, value, '\0', -1));
				return i;
			}
			else
			{
				out.push_back(in[i]);
				i++;
			}
		}
		return right;
	}

	long calculator(vector<morpheme>& v,int left,int right)
	{
		vector<morpheme> r1;
		long curvalue = 0;
		for (int i = left; i < right;)
		{
			if (v[i].type == -1)
			{
				curvalue = v[i].digital;
				i++;
			}
			else if (v[i].priority == 3)
			{
				curvalue = curvalue * v[i + 1].digital;
				i += 2;
			}
			else if (v[i].priority == 4)
			{
				curvalue = curvalue / v[i + 1].digital;
				i += 2;
			}
			else
			{
				r1.push_back(morpheme(-1, curvalue, '\0', -1));
				r1.push_back(v[i]);
				i++;
			}
		}
		r1.push_back(morpheme(-1, curvalue, '\0', -1));

		long result = 0;
		curvalue = 0;
		for (int i = 0; i < r1.size();)
		{
			if (r1[i].type == -1)
			{
				curvalue = r1[i].digital;
				i++;
			}
			else if (r1[i].priority == 1)
			{
				curvalue = curvalue + r1[i + 1].digital;
				i += 2;
			}
			else if (r1[i].priority == 2)
			{
				curvalue = curvalue - r1[i + 1].digital;
				i += 2;
			}
			else
			{
				break;
			}
		}

		result = curvalue;
		return result;
	}
    int calculate(string s) {
		string str = s;
		str = skipspace(str);
		vector<morpheme> in;
		scanning(str, in);
		vector<morpheme> out;
		recursive(out,in, 0, in.size());
		long result = calculator(out, 0, out.size());
        return result;
    }
};
阅读全文 »

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

正则表达式

题目

- 44. 通配符匹配

静态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
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
class Solution {
public:
  vector<int> kmp(string p)
  {
    vector<int> next(p.length() + 1,0);

    for (int i = 0; i < p.length() + 1; i++)
    {
      if (i == 0 || p[i - 1] == '*')
      {
        next[i] = i;
        continue;
      }
      for (int j = i - 1; j >= 0; j--)
      {
        bool flag = true;
        for (int k = j-1; k >= 0; k--)
        {
          if (p[k] == '*')
          {
            break;
          }
          else if (p[k] != p[i - (j - k)] && p[k] != '?' && p[i - (j - k)] != '?')
          {
            flag = false;
            break;
          }
        }
        if (flag == true)
        {
          next[i] = j;
          break;
        }
      }
    }
    return next;
  }
  bool isMatch(string s, string p) {
    if (p.empty())
    {
      if (s.empty())
      {
        return true;
      }
      else
      {
        return false;
      }
    }
    vector<int> next = kmp(p);
    int index = 0;
    for (int i = 0; i < s.length();)
    {
      if (index == 0 && i > 0)
      {
        break;
      }
      else if (index != p.length() && p[index] == '?')
      {
        i++;
        index++;
      }
      else if (index == p.length() && p[p.length() - 1] == '*')
      {
        break;
      }
      else if (index != p.length() && p[index] == '*')
      {
        index++;
      }
      else if (index != p.length() && s[i] == p[index])
      {
        i++;
        index++;
      }
      else if (index != p.length() && index == next[index])
      {
        i++;
      }
      else
      {
        int ii;
        int jj;
        bool flag = false;
        while (!flag)
        {
          ii = index;
          index = next[index];
          jj = index;
          flag = true;
          for (int k = jj - 1; k >= 0; k--)
          {
            if (p[k] == '*')
            {
              break;
            }
            if (p[ii - jj + k] == '?' && p[k] != '?')
            {
              if (p[k] != s[i - (jj - k)])
              {
                flag = false;
                break;
              }
            }

            if (k == 0 && i - (jj - k) > 0)
            {
              flag = false;
              break;
            }
          }
        }
      }
    }
    while (p[index] == '*')
    {
      index++;
    }
    if (index == p.length())
    {
      return true;
    }
    else
    {
      return false;
    }
  }
};
阅读全文 »

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

正则表达式

题目

- 44. 通配符匹配

动态规划

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
class Solution {
public:
    bool isMatch(string s, string p) {
        vector<vector<bool>> dp;
		dp.resize(s.length() + 1, vector<bool>(p.length() + 1));

		dp[0][0] = true;
		for (int j = 1; j < p.length() + 1; j++)
		{
			if (p[j - 1] == '*')
			{
				dp[0][j] = dp[0][j - 1];
			}
		}
		for (int i = 1; i < s.length() + 1; i++)
		{
			for (int j = 1; j < p.length() + 1; j++)
			{
				if (p[j - 1] == '*')
				{
					dp[i][j] = dp[i - 1][j - 1] || dp[i][j - 1] || dp[i - 1][j];
				}
				else if (s[i - 1] == p[j - 1] || p[j - 1] == '?')
				{
					dp[i][j] = dp[i - 1][j - 1];
				}
				else
				{
					dp[i][j] = false;
				}
			}
		}
		return dp[s.length()][p.length()];
    }
};
阅读全文 »

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

计算器

题目

- leetcode 224. 基本计算器

栈

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
class Solution {
  public:
      struct element
      {
          unsigned long digital;
          char operatorcharacter;
          int type;
          element(int t, int d, char o)
          {
              type = t;
              digital = d;
              operatorcharacter = o;
          }
      };
      int calculate(string s) {
          char operatorcharacter[] = { ')','-','+','*','/','(' };
          int operatorcharacterlength = 6;
          vector<element> vectorElement;
          unsigned long digit = -1;
          int len = s.length();
          int digitpm = 1;
          element epr(0, 0, '0');
          for (int i = 0; i < len; i++)
          {
              char c = s[i];
              for (int j = 0; j < operatorcharacterlength; j++)
              {
                  if (c == operatorcharacter[j])
                  {
                      if (digit != -1)
                      {
                          vectorElement.push_back(element(2, digitpm * digit,'0'));
                          digit = -1;
                          digitpm = 1;
                          epr = vectorElement.back();
                      }

                      if (digitpm == -1)
                      {
                          vectorElement.push_back(element(1, 0, '-'));
                          digitpm = 1;
                      }

                     if (c == '-' && epr.type == 0)
                      {
                          digitpm = -1;
                      }
                      else if(c == '-' && epr.type == 1 && epr.operatorcharacter == '(')
                      {
                          digitpm = -1;
                      }
                      else
                      {
                          digitpm = 1;
                          vectorElement.push_back(element(1, -1, c));
                          epr = vectorElement.back();
                      }
                      break;
                  }
              }

              if ((int)c >= 0x30 && (int)c <= 0x39)
              {
                  if (digit == -1)
                  {
                      digit = (int)c - 0x30;
                  }
                  else
                  {
                      digit = digit * 10 + (int)c - 0x30;
                  }
              }
          }
          if (digit != -1)
          {
              vectorElement.push_back(element(2, digitpm * digit, '0'));
          }
          for (unsigned int i = 0; i < vectorElement.size(); i++)
          {
              element e ( vectorElement[i]);
              if (e.type == 1)
              {
                  //cout << "index:" << i << "	value:" << e.operatorcharacter << endl;
              }
              else
              {
                  //cout << "index:" << i << "	value:" << e.digital << endl;
              }
          }

          stack<unsigned long> stackDigital;
          stack<char> stackOperator;

          for (int i = 0; i < vectorElement.size(); i++)
          {
              element e  = vectorElement[i];

              if (e.type == 2)
              {
                  stackDigital.push(e.digital);
              }
              else
              {
                  char c = e.operatorcharacter;
                  if (c == ')' && stackOperator.top() == '(')
                  {
                      stackOperator.pop();
                  }
                  else
                  {
                      while (stackOperator.size()>0)
                      {
                          char cpr = stackOperator.top();
                          if (c == ')' && stackOperator.top() == '(')
                          {
                              stackOperator.pop();
                              break;
                          }
                          int indexc, indexcpr;
                          for (int j = 0; j < operatorcharacterlength; j++)
                          {
                              if (operatorcharacter[j] == c)
                              {
                                  indexc = j;
                              }
                              if (operatorcharacter[j] == cpr)
                              {
                                  indexcpr = j;
                              }
                          }

                          bool flag = false;
                          if (indexc == indexcpr && (indexcpr == 1 || indexcpr == 2 || indexcpr == 3 || indexcpr == 4))
                          {
                              flag = true;
                          }
                          else if ((indexc == 1 || indexc == 2) && (indexcpr == 1 || indexcpr == 2 || indexcpr == 3 || indexcpr == 4))
                          {
                              flag = true;
                          }
                          else if ((indexc == 3 || indexc == 4) && (indexcpr == 3 || indexcpr == 4))
                          {
                              flag = true;
                          }
                          else if (indexc == 0 && cpr != '(')
                          {
                              flag = true;
                          }
                          else if (indexc < indexcpr && cpr != '(')
                          {
                              flag = true;
                          }

                          if (flag == true)
                          {
                              unsigned long b = stackDigital.top();
                              stackDigital.pop();
                              unsigned long a = stackDigital.top();
                              stackDigital.pop();

                              char o = stackOperator.top();
                              stackOperator.pop();

                              unsigned long c = 0;
                              if (o == '+')
                              {
                                  c = a + b;
                              }
                              else if (o == '-')
                              {
                                  c = a - b;
                              }
                              else if (o == '*')
                              {
                                  c = a * b;
                              }
                              else if (o == '/')
                              {
                                  c = a / b;
                              }
                              //cout << "abc:" << a << o <<b <<"="<<c << endl;
                              stackDigital.push(c);
                          }
                          else
                          {
                              break;
                          }
                      }

                      if (c == ')')
                      {
                      }
                      else
                      {
                          stackOperator.push(e.operatorcharacter);
                      }
                  }
              }
          }

          while (stackOperator.size() > 0)
          {

              unsigned long b = stackDigital.top();
              stackDigital.pop();

              unsigned long a = 0;
              if (stackDigital.size() == 0)
              {
                  a = 0;
              }
              else
              {
                  a = stackDigital.top();
                  stackDigital.pop();
              }

              char o = stackOperator.top();
              stackOperator.pop();

              unsigned long c = 0;
              if (o == '+')
              {
                  c = a + b;
              }
              else if (o == '-')
              {
                  c = a - b;
              }
              else if (o == '*')
              {
                  c = a * b;
              }
              else if (o == '/')
              {
                  c = a / b;
              }
              //cout << "abc:" << a << o << b << "=" << c << endl;
              stackDigital.push(c);
          }
          if (stackOperator.empty() && stackDigital.size() == 1)
          {
              return stackDigital.top();
          }
          else
          {
              cout << "error" << endl;
              return 0;
          }
      }
  };
阅读全文 »

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

零钱兑换

322.零钱兑换

剪枝

当 amount==0amount==0 时剪枝，因为大面值硬币需要更多小面值硬币替换，继续减少一枚或几枚大硬币搜索出来的答案【如果有】肯定不会更优。

当 amount!=0，但已经使用的硬币数 cnt 满足了 cnt+1>=ans 时剪枝，因 amount 不为 0，至少还要使用 1 枚硬币，则继续搜索得到的答案不会更优。是 break 不是 continue，因为少用几枚面值大的硬币搜索出的方案【如果有】肯定需要更多枚面值小的硬币来替换掉这枚大的硬币【同剪枝 1 理由】，而使用这几枚大的硬币都搜索不到更好的解，故应该是 break。

代码

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
class Solution {
public:
  int ans = INT_MAX;
  void dfs( vector<int>& coins, int amount,int index,int cnt)
  {
    if (index < 0) {
      return;
    }
    for (int c = amount / coins[index]; c >= 0; c--)
    {
      int na = amount - c * coins[index];
      int ncnt = cnt + c;
      if (na == 0) {
        ans = ncnt < ans ? ncnt : ans;
        break;//剪枝1
      }
      if (ncnt + 1 >= ans) {
        break; //剪枝2
      }
      dfs(coins, na, index - 1, ncnt);
    }
  }
  int coinChange(vector<int>& coins, int amount) {
    sort(coins.begin(), coins.end());

    dfs( coins, amount, coins.size() - 1,0);
    if (ans == INT_MAX)
    {
      return -1;
    }
    return ans;
  }
};
阅读全文 »

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

正则表达式

题目

- 44. 通配符匹配

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
class Solution {
public:
  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;
  }
  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;
  }
};
阅读全文 »