Sadə sətirlər

Sıra sadə sayılır, əgər o, öz sufikslərindən hər hansı birindən leksikoqrafik olaraq kiçikdirsə. Bundan əlavə, tək bir simvoldan ibarət sıra da sadə hesab olunur. Məsələn, $a$, $abb$, $aabb$ və $abac$ sadədir, lakin $aa$, $baa$, $acab$ və $abcabc$ sadə deyil.

Məlumdur ki, istənilən sıra leksikoqrafik olaraq azalan ardıcıllıqla sadə sıraların konkatenasiyasına yeganə şəkildə parçalanır. Bu parçalanmanı tapan proqram yazmaq lazımdır.