首页 > ACM题库 > HDU-杭电 > Hdu 1797 Match the string 待解决 [解题报告] C++
2013
12-23

Hdu 1797 Match the string 待解决 [解题报告] C++

Match the string

问题描述 :

  Sometimes we need to check that if a given string matches a format string or not. Look at the format string: (a)*(b)+(c)?(f|d), * represents the substring in the brackets before appears any times, if the format string is (ab)* ,then string “ababab” or null string match the format string .And + represents the substring in the brackets appears one or more times, for the format (ab)+ , the null string can’t match the format string. And the ? represents the substring in the brackets before appears none or once , and when you get the symbol |, either the substring s1(left of the symbol | ) appear once, or the substring s2(right of the symbol) appear once, but they don’t appear together. For example, (f|h) represent that either ‘f’ or ‘h’ appears for once.

输入:

  In the first line, there is N represents the case number. Then N lines follow, in each line, there is a string. The length of each string won’t exceed 100000, and 1<=N<=1000. The letters appear in the string are only lower letters.

输出:

  The format string is given before and won’t be changed. The format string is (a)*aba((b)?(d)+)?h((f)|(k))+
  For each case, just print “YES” if the input string mathes the format string, or “NO”.

样例输入:

4
abahf
aababdddhffkk
babbbdh
aaaaaaaaabahffffffff

样例输出:

YES
YES
NO
YES


  1. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.