Longest repeated substring problem
કોમ્પ્યુટર વિજ્ઞાનમાં, સૌથી લાંબી પુનરાવર્તિત સબસ્ટ્રિંગ સમસ્યા એ સ્ટ્રિંગની સૌથી લાંબી સબસ્ટ્રિંગ શોધવાની સમસ્યા છે જે ઓછામાં ઓછી બે વાર થાય છે. આ સમસ્યાને રેખીય સમય અને અવકાશમાં શબ્દમાળા માટે પ્રત્યય વૃક્ષ બનાવીને ('$' જેવા વિશિષ્ટ તારના અંતના પ્રતીક સાથે) અને એકથી વધુ બાળકવાળા વૃક્ષમાં સૌથી ઊંડો આંતરિક નોડ શોધીને ઉકેલી શકાય છે. ઊંડાઈ મૂળમાંથી પસાર થયેલા અક્ષરોની સંખ્યા દ્વારા માપવામાં આવે છે. મૂળથી આવા નોડ સુધી ધાર દ્વારા જોડાયેલી સ્ટ્રિંગ સૌથી લાંબી પુનરાવર્તિત સબસ્ટ્રિંગ છે. ઓછામાં ઓછી ઘટનાઓ સાથે સૌથી લાંબી સબસ્ટ્રિંગ શોધવાની સમસ્યાનું સમાધાન દરેક આંતરિક નોડ માટે પાંદડાના વંશજોની સંખ્યાની ગણતરી કરવા માટે પહેલા વૃક્ષની પ્રક્રિયા કરીને અને પછી ઓછામાં ઓછા પાંદડાના વંશજો સાથે સૌથી ઊંડો નોડ શોધીને કરી શકાય છે. ઓવરલેપિંગ પુનરાવર્તન ટાળવા માટે, તમે ચકાસી શકો છો કે પ્રત્યય લંબાઈની સૂચિમાં ઉપસર્ગ-લંબાઈના તફાવત કરતાં ઓછા સાથે કોઈ ક્રમિક ઘટકો નથી. સ્ટ્રિંગ "ATCGATCGA $" સાથેની આકૃતિમાં, સૌથી લાંબી સબસ્ટ્રિંગ જે ઓછામાં ઓછી બે વાર પુનરાવર્તન કરે છે તે "ATCGA" છે. બાહ્ય કડીઓ સી પ્રત્યય વૃક્ષનો ઉપયોગ કરીને સૌથી લાંબી પુનરાવર્તિત સબસ્ટ્રિંગનું અમલીકરણ ઓનલાઇન ડેમોઃ શબ્દમાળાઓ પર સૌથી લાંબી પુનરાવર્તિત સબસ્ટ્રિંગ સમસ્યાઓ ઔપચારિક ભાષાઓ સંયોજન