HDU 6170 Two strings

本文由 Ocrosoft 于 2017-08-22 18:32:20 发表

Two strings

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 149    Accepted Submission(s): 42

Problem Description
Giving two strings and you should judge if they are matched.
The first string contains lowercase letters and uppercase letters.
The second string contains lowercase letters, uppercase letters, and special symbols: “.” and “*”.
. can match any letter, and * means the front character can appear any times. For example, “a.b” can match “acb” or “abb”, “a*” can match “a”, “aa” and even empty string. ( “*” will not appear in the front of the string, and there will not be two consecutive “*”.
 

Input
The first line contains an integer T implying the number of test cases. (T≤15)
For each test case, there are two lines implying the two strings (The length of the two strings is less than 2500).
 

Output
For each test case, print “yes” if the two strings are matched, otherwise print “no”.
 

Sample Input
	
3 aa a* abb a.* abb aab
 

Sample Output
	
yes yes no
 

Solution
2017 Multi-University Training Contest – Team 9
乱搞,根本没有看出来这是个三维DP,拿到题目一眼觉得这不是正则表达式么,然后上来撸了三行交了,WA,不知道错哪去翻讨论版,没想到这题目.*竟然只能匹配相同的字符,也就是a.*能匹配abb而不能匹配abc,那这样发现正则不好搞了,翻了一会儿讨论版突然想到,正则要实现这个功能,分组就好了,a.*转换成正则就是a(.)\1*,a.*b.*转换是a(.)\1*b(.)\2*,\xx*表示前面那个括号内容重复任意次。然后就过了…

#define C11
#include <set>
#include <map>
#include <stack>
#include <string>
#include <cstdio>
#include <queue>
#include <vector>
#include <cmath>
#include <climits>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#ifdef C11
#include <tuple>
#include <regex>
#include <random>
#include <complex>
#endif
using namespace std;
/** const var def */
const double eps = 1e-8;
const int maxn = 2500 + 10;
const int MAXN = maxn * 10;
const int MOD = 1000000007;
const double PI = 4 * atan(1.0);
/** type def */
typedef long long LL;
typedef pair<int, int> Pii;
typedef pair<LL, LL> Pll;
typedef vector<int> Vi;
typedef pair<double, double> Vec2;
#ifdef C11
using Vec3 = tuple<double, double, double>;
using Tp3 = tuple<int, int, int>;
#endif
/** easy def */
#define _link(x) x&&x
#define ms(a) memset(a,0,sizeof(a))
#define msr(a) memset(a,-1,sizeof(a))
/* first, second, position */
#define _f first
#define _s second
#define _p(_tp,_pos) get<_pos>(_tp)
/* operator */
Pii operator +(const Pii &x, const Pii &y) { return Pii(x.first + y.first, x.second + y.second); }
Pii operator -(const Pii &x) { return Pii(-x.first, -x.second); }
Pii operator -(const Pii &x, const Pii &y) { return x + (-y); }
Pii operator +=(Pii &x, const Pii &y) { return x = x + y; }
Pii operator -=(Pii &x, const Pii &y) { return x = x - y; }
#pragma region input&output
template<class T>inline T read(T &num)
{
	char CH; bool F = false;
	for (CH = getchar(); CH<'0' || CH>'9'; F = CH == '-', CH = getchar());
	for (num = 0; CH >= '0'&&CH <= '9'; num = num * 10 + CH - '0', CH = getchar());
	F && (num = -num);
	return num;
}
template<class T>inline T read()
{
	T num;
	return read(num);
}
#ifdef C11
template<class T, class... Args>inline int read(T &t, Args &...args)
{
	read(t);
	read(args...);
	return t;
}
#endif
template<class T> inline void print(T p, char ed = '\n')
{
	int stk[70], tp = 0;
	if (p < 0) { putchar('-'); p = -p; }
	if (!p) { putchar('0'); if (ed != '\0')putchar(ed); return; }
	while (p) stk[++tp] = p % 10, p /= 10;
	while (tp) putchar(stk[tp--] + '0');
	if (ed != '\0')putchar(ed);
}
#ifdef C11
template<class T, class... Args>inline void print(T t, Args ...args)
{
	print(t, '\0');
	if (sizeof...(args))putchar(' ');
	else putchar('\n');
	print(args...);
}
#endif
#pragma endregion

int main()
{
	int n = read<int>(); getchar();
	while (n--)
	{
		string str, pat, pattern;
		getline(cin, str); getline(cin, pat);
		int groupCnt = 1;
		for (auto it = begin(pat); it != end(pat); it++)
		{
			if (*it == '*'&&*(it - 1) == '.')pattern += "(.)\\" + to_string(groupCnt++) + "*";
			else pattern += *it;
		}
		if (regex_match(str, regex(pattern)))printf("yes\n");
		else printf("no\n");
	}
	return 0;
}

 

欢迎转载,请保留出处与链接。Ocrosoft » HDU 6170 Two strings

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址