字符串匹配有限自动机习题

模式字符串P=abcabcba,就此构造出相应的字符串匹配自动机

P = abcabcba
P0 = ε
P1 = a
P2 = ab
P3 = abc
P4 = abca
P5 = abcab
P6 = abcabc
P7 = abcabcb
P8 = abcabcba

σ(a) = 1               a
σ(b) = 0
σ(c) = 0

σ(aa) = 1              a
σ(ab) = 2              ab
σ(ac) = 0        

σ(aba) = 1             a
σ(abb) = 0              
σ(abc) = 3             abc

σ(abca) = 4            abca
σ(abcb) = 0              
σ(abcc) = 0              

σ(abcaa) = 1           a
σ(abcab) = 5           abcab              
σ(abcac) = 0 
           
σ(abcaba) = 1          a
σ(abcabb) = 0                            
σ(abcabc) = 6          abcabc              

σ(abcabca) = 4         abca
σ(abcabcb) = 7         abcabcb                            
σ(abcabcc) = 0                  

σ(abcabcba) = 8        abcabcba
σ(abcabcbb) = 0                                          
σ(abcabcbc) = 0 

           input    
state    a  b  c   P
  0      1  0  0   a
  1      1  2  0   b
  2      1  0  3   c
  3      4  0  0   a
  4      1  5  0   b
  5      1  0  6   c
  6      4  7  0   b
  7      8  0  0   a

image