64 lines
1.7 KiB
Python
64 lines
1.7 KiB
Python
|
import sys
|
||
|
|
|
||
|
|
sys.setrecursionlimit(4500)
|
||
|
|
|
||
|
|
def AddTransition(transitions, state_from, state_to, symbol):
|
||
|
|
if state_from in transitions:
|
||
|
|
if symbol not in transitions[state_from]:
|
||
|
|
transitions[state_from][symbol] = {state_to}
|
||
|
|
else:
|
||
|
|
transitions[state_from][symbol] |= {state_to}
|
||
|
|
else:
|
||
|
|
transitions[state_from] = {symbol: {state_to}}
|
||
|
|
|
||
|
|
def AddFinalState(final_states, state):
|
||
|
|
final_states.add(state)
|
||
|
|
|
||
|
|
def GetFinalState(transitions, final_states, string, current_state):
|
||
|
|
if not string:
|
||
|
|
return current_state if current_state in final_states else -1
|
||
|
|
|
||
|
|
symbol, rest = string[0], string[1:]
|
||
|
|
|
||
|
|
try:
|
||
|
|
for state in transitions[current_state][symbol]:
|
||
|
|
result = GetFinalState(transitions, final_states, rest, state)
|
||
|
|
if result != -1:
|
||
|
|
return result
|
||
|
|
except KeyError:
|
||
|
|
return -1
|
||
|
|
|
||
|
|
return -1
|
||
|
|
|
||
|
|
def IsAccepted(transitions, finalStates, string, initial_state):
|
||
|
|
finalState = GetFinalState(transitions, finalStates, string, initial_state)
|
||
|
|
return finalState in finalStates
|
||
|
|
|
||
|
|
|
||
|
|
transitions = {}
|
||
|
|
finalStates = {3}
|
||
|
|
|
||
|
|
AddTransition(transitions, 0, 0, 'b')
|
||
|
|
AddTransition(transitions, 0, 0, 'c')
|
||
|
|
AddTransition(transitions, 0, 1, 'a')
|
||
|
|
AddTransition(transitions, 1, 1, 'a')
|
||
|
|
AddTransition(transitions, 1, 0, 'c')
|
||
|
|
AddTransition(transitions, 1, 2, 'b')
|
||
|
|
AddTransition(transitions, 2, 1, 'a')
|
||
|
|
AddTransition(transitions, 2, 0, 'b')
|
||
|
|
AddTransition(transitions, 2, 3, 'c')
|
||
|
|
AddTransition(transitions, 3, 3, 'a')
|
||
|
|
AddTransition(transitions, 3, 3, 'b')
|
||
|
|
AddTransition(transitions, 3, 3, 'c')
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
for line in sys.stdin:
|
||
|
|
line = line.rstrip()
|
||
|
|
|
||
|
|
if IsAccepted(transitions, finalStates, line, 0):
|
||
|
|
print('YES')
|
||
|
|
else:
|
||
|
|
print('NO')
|
||
|
|
|