作者yauhh (哟)
看板Prob_Solve
标题Re: [问题] reduce, 字串, hash
时间Sat Sep 15 01:48:58 2012
※ 引述《wsx02 ()》之铭言：
: 2. 字串 http://ppt.cc/GL16
: 请问有人知道这个问题应该解吗?
Q: Given a string S, and we determine if the string S satisfies the
following conditions
a. S contains repeated characters such as xxxyy form (x and y are
characters) ...
就是用状态机解决. "xxxyy" 生成状态有六种:
S0: ""
S1: "x"
S2: "xx"
S3: "xxx"
S4: "xxxy"
S5: "xxxyy"
由 S1, S2 依顺序到 S5, 每个状态都是前一个状态尾端加一个文字.
参与这个状态机的资料分为三类: 'x', 'y', 最後 / 代表非 'x' 也非 'y'的
其他文字. 我说 Sn 状态遇到某个文字 m, 要跑到 Sn+ 状态, 是以下列式子表达:
Sn(m) = Sn+
这样的式子叫做状态转换. 一个状态转换会代表一种情况 c, 把情况 c 加进以上
式子,写成
(Sn(m) = Sn+): c
叫做从 Sn 状态遇到某个文字 m, 结果跑到 Sn+ 状态, 并且抛回一个 c 代表是否
完成. 然後,我会列出以下的状态转换来用.
(S0('x') = S1): false
(S0('y'), S0(/) = S0): false
(S1('x') = S2): false
(S1('y'), S1(/) = S0): false
(S2('x') = S3): false
(S2('y'), S2(/) = S0): false
(S3('x') = S3): false
(S3('y') = S4): false
(S3(/) = S0): false
(S4('x'), S4(/) = S0): false
(S4('y') = S0): true
(S5('x') = S1): false
(S5('y'), S5(/) = S0): false
实作上我会用一个常值字串 "xxxyy", 用一个整数 len 描述六种状态的文字长度.
用类似 C 语言的写法:
char[] state_str = "xxxyy"
enum state { S0, S1, S2, S3, S4, S5 };
enum state len = S0;
bool transit(char m) {
bool result = false;
switch (len) {
case S0:
if (m = 'x')
len = S1;
else
len = S0;
break;
case S1:
if (m = 'x')
len = S2;
else
len = S0;
break;
case S2:
if (m = 'x')
len = S3;
else
len = S0;
break;
case S3:
if (m = 'x')
len = S3;
else if (m = 'y')
len = S4;
else
len = S0;
break;
case S4:
len = S0;
if (m = 'y') result = true;
break;
case S5:
if (m = 'x')
len = S1;
else
len = S0;
break;
}
return result;
}
所以判断式可以这样写:
bool contain(char[] S, char[] xxxyy = "xxxyy") {
int i;
bool result;
xxxyy = "xxxyy";
len = S0;
for (i=0; i< strlen(S); i++) {
result = transit(S[i]);
if (result == true) break;
}
return result;
}
当然,这样只回答 "xxxyy" 格式并不够. 题目中讲的格式是 "such as xxxyy form,"
答题最好是再上一层,可以随着格式不同,程式自己定义状态转换规则.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 36.226.98.45
1F：推 wsx02:谢谢 09/16 22:56