PTT數位生活區 / RegExp (正規表示式 Regular Expression)

Re: [問題] 連續a跟奇數b..

看板RegExp (正規表示式 Regular Expression)作者LPH66 (IWH68S0XZ8M89)時間17年前 (2008/04/20 18:57)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串4/4 (看更多)

我來試著硬拆好了 ※ 引述《LPH66 (IWH68S0XZ8M89)》之銘言： : (a(bb)*a)*(b|ab(bb)*a)((a(bb)*a)*|(b|ab(bb)*a)(a(bb)*a)*(b|ab(bb)*a))* 整個式子是 R*G(R*|GR*G)* 的結構表示整個式子相當於拆成用G分隔的段然後第一個G抓住前面的一堆R (R*G) 後面兩個G一組抓住其中的一堆R (GR*G) 在組與組之間的一堆R則由R*抓住 (也就是式子表示為一堆R和G的組合其中G有奇數個從後面兩個兩個G一組拆開) 從字串本身來看的話我們可以照字串中兩個a一組中間劃分開來 (因為一個R或一個G有0或2個a 而由於a有偶數個必然不會有落單的) 例如: aaaaabbbbaaaaaabbbaaa => aa aa abbbba aa aa abbba aa abbbbbaaababa => abbbbba aa b aba aabbbbbaaaaabbbba => aa bbbbb aa aa abbbba abbabbaba => abba bb aba abababababa => aba b aba b aba 然後把所有是兩個a之中有偶數個b的部份代換成R 其他的代換成G 由於b有奇數個而代換成R的部份必然一共用去了偶數個b 因此剩下的b有奇數個然後也只剩下了 (1)連續奇數個b (2)兩個a中間有奇數個b 因此代換成一個G的一段必然有奇數個b 因此全部必然有奇數個G 正好符合上面所提到的型式 (全部有奇數個G 兩兩間有0或多個R) 於是R就是(a(bb)*a) G就是(b(bb)*|ab(bb)*a) 之所以上面的G是(b|ab(bb)*a)的理由是取奇數個b一組和取一個b一組是一樣的這相當於上面的分組中把只有一串b的拆成一個b一段例如: aabbbbbaaaaabbbba => aa b b b b b aa aa abbbba abbabbaba => abba b b aba 這樣G仍然會是奇數個由於所有這樣的字串這樣拆完再代換完必然是如此型式所以就可以用上面的R,G表示把R,G代入對應字串就得到原式反之不合的這樣拆必然出問題 --- 這樣一分析的話就可以得到另一種稍微直覺的寫法: RG組合,G奇數個可以寫成 R*GR*(GR*GR*)* 這樣就成了 (a(bb)*a)*(b|ab(bb)*a)(a(bb)*a)*((b|ab(bb)*a)(a(bb)*a)*(b|ab(bb)*a)(a(bb)*a)*)* 比上一個稍長但仍然符合要求 -- 'You've sort of made up for it tonight,' said Harry. 'Getting the sword. Finishing the Horcrux. Saving my life.' 'That makes me sound a lot cooler then I was,' Ron mumbled. 'Stuff like that always sounds cooler then it really was,' said Harry. 'I've been trying to tell you that for years.' -- Harry Potter and the Deathly Hollows, P.308 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.30.84