regex - JAVA Regex が特定のパターンで停止する

Question

正規表現パターンを照合しようとするたびに

    PREREQasdasdasdasdsadNot+es3adadaK2+0000000+043YEARA_

と

    ^([a-zA-Z0-9]*|(([a-zA-Z0-9])+(([_]*|[-]|[+])[a-zA-Z0-9]+)*))$

吊るされる

これらは役立つかもしれないいくつかのケースです

• 陽性例

1. asdsadas+asd-asdasdad-asdad+asdasd
2. UPGRADE+asd-asdasdasdvf-asd
3. UPGRADE+asd-adsasda__LS-TasdL+asdasdwd
4. UPGRADE+asd-asdasd__LS-TRI+A+L+asdasdwd
5. UPG-R-ADE+asd-asd__LS-TRI+A+L+asdasdwd
6. PREREQ+asdasdasda-Traveler-asd3YEAR+FK20000000043YEAR-A
7. PREREQ+asdasdd-T_raveler-asdasds3YEAR+FK20000000043YEAR-A
8. UP_G-R+ADE+asd-ESS__________E+N+T-I_A_LS-TRI+A+L+asdasdwd
9. PREREQ+asdad-Traveler-asdasd3YEAR+FK200__0-0+0_00043YEAR-A
10. PREREQasdasdasdTravelerasda3YEARFK20000000043YEARA
11. UP_G-R+ADE+MTG-ESSENTIA__LS-TRI+A+L+asdasdwd
12. PREREQasdasdasdasdvfTravelerasdt+esasd2K2+0000000+043YEARA

陰性例

1. UPG--RADE+asdasd-asdasdasd__LS-TRI+A+L+asdasdwd
2. UPG-R-ADE_+_asda-asdasdasd__LS-TRI+A+L+asdasdwd
3. UPG-R-ADE+_asd-asdasdad__LS-TRI+A+L+asdasdwd
4. UPG-R-ADE+_asd-ESSENTIA__LS-TRI+A+L+asdasdwd
5. PREREQ+asdasdasdasdvf-asdr-asd++3YEAR+FK20000000043YEAR-A
6. PREREQ_+-asdasdasdasdvf-asdr-Notes3YEAR+-+FK20000000043YEAR-A
7. _PREREQ+asdasdasdasdvf-asdr-asd3asdR+FK200__0-0+0_00043YEAR-A

システムがハングする (NEG ケース)

1. PREREQ+asdasdasdasdvf-asd-asd3YEAR+-+FK20000000043asdds-A
2. PREREQasdasdasdasdvfasdrNot+es3YEARFK2+0000000+043asdasd_

Answer 1

修正済み (およびテスト済み)

それを見て：

^
(
    [a-zA-Z0-9]*
    |
    (
        ([a-zA-Z0-9])+
        (
            ([_]*|[-]|[+])
            [a-zA-Z0-9]+
        )*
    )
)
$

次のように単純化できます。

^(
    [a-zA-Z0-9]+
    (
        ([_]+|[-+])
        [a-zA-Z0-9]+
    )*
)?$

ここで、そうでなければアンダースコアがループのたびにすべての位置に収まるように修正_*しました：指数関数的。_+ハングの原因: (_* ...)*。

   ^([a-zA-Z0-9]+(([_]+|[-+])[a-zA-Z0-9]+)*)?$

残念ながら、正規表現はそのようなことで失敗します。ほとんど停止問題のようなものです。