Lexicographically minimal string rotation
ಗಣಕಯಂತ್ರ ವಿಜ್ಞಾನದಲ್ಲಿ, ಲೆಕ್ಸಿಕೋಗ್ರಾಫಿಕ್ ಆಗಿ ಕನಿಷ್ಠ ಸ್ಟ್ರಿಂಗ್ ತಿರುಗುವಿಕೆ ಅಥವಾ ಲೆಕ್ಸಿಕೋಗ್ರಾಫಿಕ್ ಆಗಿ ಕನಿಷ್ಠ ವೃತ್ತಾಕಾರದ ಸಬ್ಸ್ಟ್ರಿಂಗ್ ಅಂತಹ ಎಲ್ಲಾ ತಿರುಗುವಿಕೆಗಳ ಕಡಿಮೆ ಲೆಕ್ಸಿಕೋಗ್ರಾಫಿಕಲ್ ಕ್ರಮವನ್ನು ಹೊಂದಿರುವ ಸ್ಟ್ರಿಂಗ್ನ ತಿರುಗುವಿಕೆಯನ್ನು ಕಂಡುಹಿಡಿಯುವ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಉದಾಹರಣೆಗೆ, ಶಬ್ದಕೋಶದ ಪ್ರಕಾರ "ಬಾಕಾದ್" ನ ಕನಿಷ್ಠ ಆವರ್ತನವು "ಅಕ್ಕಾದ್ದ್ಬ್" ಆಗಿರುತ್ತದೆ. ಒಂದು ಸ್ಟ್ರಿಂಗ್ ಅನೇಕ ಲೆಕ್ಸಿಕೊಗ್ರಾಫಿಕಲ್ ಕನಿಷ್ಠ ತಿರುಗುವಿಕೆಗಳನ್ನು ಹೊಂದಲು ಸಾಧ್ಯವಿದೆ, ಆದರೆ ಹೆಚ್ಚಿನ ಅಪ್ಲಿಕೇಶನ್ಗಳಿಗೆ ಇದು ಮುಖ್ಯವಲ್ಲ ಏಕೆಂದರೆ ತಿರುಗುವಿಕೆಗಳು ಸಮಾನವಾಗಿರಬೇಕು. ಪದವಿನ್ಯಾಸದ ಪ್ರಕಾರ ಕನಿಷ್ಠ ತಿರುಗುವಿಕೆಯನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ತಂತಿಗಳನ್ನು ಸಾಮಾನ್ಯಗೊಳಿಸುವ ಮಾರ್ಗವಾಗಿ ಉಪಯುಕ್ತವಾಗಿದೆ. ತಂತಿಗಳು ಗ್ರಾಫ್ಗಳಂತಹ ಸಂಭಾವ್ಯ ಐಸೊಮಾರ್ಫಿಕ್ ರಚನೆಗಳನ್ನು ಪ್ರತಿನಿಧಿಸಿದರೆ, ಈ ರೀತಿಯಲ್ಲಿ ಸಾಮಾನ್ಯೀಕರಿಸುವುದು ಸರಳ ಸಮಾನತೆಯ ಪರಿಶೀಲನೆಗೆ ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ. ವೃತ್ತಾಕಾರದ ತಂತಿಗಳೊಂದಿಗೆ ವ್ಯವಹರಿಸುವಾಗ ಸಾಮಾನ್ಯ ಅನುಷ್ಠಾನ ತಂತ್ರವೆಂದರೆ ಸ್ಟ್ರಿಂಗ್ ಸೂಚ್ಯಂಕಗಳಲ್ಲಿ ಮಾಡ್ಯುಲರ್ ಅಂಕಗಣಿತವನ್ನು ನಿರ್ವಹಿಸುವ ಬದಲು ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಸ್ವತಃ ಸಂಯೋಜಿಸುವುದು. ಅಲ್ಗಾರಿದಮ್ಗಳು ನೈವ್ ಅಲ್ಗಾರಿದಮ್ ಒಂದು ಸ್ಟ್ರಿಂಗ್ನ ಲೆಕ್ಸಿಕೋಗ್ರಾಫಿಕಲ್ ಕನಿಷ್ಠ ತಿರುಗುವಿಕೆಯನ್ನು ಕಂಡುಹಿಡಿಯುವ ನಿಷ್ಕಪಟ ಅಲ್ಗಾರಿದಮ್, ಎದುರಾದ ಅತ್ಯಂತ ಲೆಕ್ಸಿಕೋಗ್ರಾಫಿಕಲ್ ಕನಿಷ್ಠ ತಿರುಗುವಿಕೆಯನ್ನು ಗಮನದಲ್ಲಿಟ್ಟುಕೊಂಡು ಸತತ ತಿರುಗುವಿಕೆಯ ಮೂಲಕ ಪುನರಾವರ್ತಿಸುವುದು. ಸ್ಟ್ರಿಂಗ್ ಉದ್ದವಾಗಿದ್ದರೆ, ಈ ಅಲ್ಗಾರಿದಮ್ ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ ಸಮಯಕ್ಕೆ ಸರಿಯಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ. ಬೂತ್ನ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಬೂತ್ (1980) ಸಮರ್ಥ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತಾಪಿಸಿದರು. ಅಲ್ಗಾರಿದಮ್ ನುಥ್-ಮೋರಿಸ್-ಪ್ರ್ಯಾಟ್ ಸ್ಟ್ರಿಂಗ್ ಸರ್ಚ್ ಅಲ್ಗಾರಿದಮ್ನಿಂದ ಮಾರ್ಪಡಿಸಿದ ಪೂರ್ವ ಸಂಸ್ಕರಣಾ ಕಾರ್ಯವನ್ನು ಬಳಸುತ್ತದೆ. ಸ್ಟ್ರಿಂಗ್ನ ವೈಫಲ್ಯದ ಕಾರ್ಯವನ್ನು ಸಾಮಾನ್ಯ ಎಂದು ಲೆಕ್ಕಹಾಕಲಾಗುತ್ತದೆ, ಆದರೆ ಗಣನೆಯ ಸಮಯದಲ್ಲಿ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ತಿರುಗಿಸಲಾಗುತ್ತದೆ ಆದ್ದರಿಂದ ಕೆಲವು ಸೂಚ್ಯಂಕಗಳನ್ನು ಸುತ್ತುವಾಗ ಒಂದಕ್ಕಿಂತ ಹೆಚ್ಚು ಬಾರಿ ಲೆಕ್ಕ ಹಾಕಬೇಕು. ವೈಫಲ್ಯದ ಕಾರ್ಯದ ಎಲ್ಲಾ ಸೂಚ್ಯಂಕಗಳನ್ನು ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಮತ್ತೆ ತಿರುಗಿಸದೆ ಯಶಸ್ವಿಯಾಗಿ ಲೆಕ್ಕಾಚಾರ ಮಾಡಿದ ನಂತರ, ಕನಿಷ್ಠ ಲೆಕ್ಸಿಕೋಗ್ರಾಫಿಕಲ್ ತಿರುಗುವಿಕೆಯನ್ನು ಕಂಡುಹಿಡಿಯಲಾಗುತ್ತದೆ ಮತ್ತು ಅದರ ಆರಂಭಿಕ ಸೂಚ್ಯಂಕವನ್ನು ಹಿಂತಿರುಗಿಸಲಾಗುತ್ತದೆ. ಅಲ್ಗಾರಿದಮ್ನ ನಿಖರತೆಯನ್ನು ಅರ್ಥಮಾಡಿಕೊಳ್ಳುವುದು ಸ್ವಲ್ಪ ಕಷ್ಟ, ಆದರೆ ಅದನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸುವುದು ಸುಲಭ. "" "ಬೂತ್ನ ಲೆಕ್ಸಿಕೋಗ್ರಾಫಿಕಲಿ ಮಿನಿಮಲ್ ಸ್ಟ್ರಿಂಗ್ ರೊಟೇಶನ್ ಅಲ್ಗಾರಿದಮ್" "". n = ಲೆನ್ (ಗಳು) f = [-1] * (2 * n) k = 0 ವ್ಯಾಪ್ತಿಯಲ್ಲಿನ j ಗೆ (1,2 * n): i = f [j-k-1] ಆದರೆ i! =-1 ಮತ್ತು s [j% n]! = s [(k + i + 1)% n]: s [j% n] <s [(k + i + 1)% n]: k = j-i = f [i] i = = ಮತ್ತು s [j% n] = s [(k + i + 1)% n]: s [j% n] <s [(k + i + 1)% n]: k = ಬೂತ್ನ ಅಲ್ಗಾರಿದಮ್ ಸಮಯಕ್ಕೆ ಸರಿಯಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ, ಸ್ಟ್ರಿಂಗ್ನ ಉದ್ದ ಎಲ್ಲಿದೆ. ಅಲ್ಗಾರಿದಮ್ ಅತ್ಯಂತ ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ ಹೆಚ್ಚಿನ ಹೋಲಿಕೆಗಳಲ್ಲಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ ಮತ್ತು ವೈಫಲ್ಯ ಕಾರ್ಯ ಕೋಷ್ಟಕವನ್ನು ಹಿಡಿದಿಡಲು ಉದ್ದದ ಸಹಾಯಕ ಸ್ಮರಣೆಯ ಅಗತ್ಯವಿರುತ್ತದೆ. ಶೀಲೋಚ್ನ ಫಾಸ್ಟ್ ಕ್ಯಾನೊನೈಸೇಶನ್ ಅಲ್ಗಾರಿದಮ್ ಶೀಲೋಚ್ (1981) ಕಾರ್ಯಕ್ಷಮತೆಯ ದೃಷ್ಟಿಯಿಂದ ಬೂತ್ನ ಫಲಿತಾಂಶವನ್ನು ಸುಧಾರಿಸುವ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತಾಪಿಸಿದರು. ಉದ್ದದ ತಂತಿಯ ಸಮಾನ ಲೆಕ್ಸಿಕೋಗ್ರಾಫಿಕಲ್ ಕನಿಷ್ಠ ತಿರುಗುವಿಕೆಗಳಿದ್ದರೆ, ದಾರವು ಉದ್ದದ ಸಮಾನ ಸಬ್ಸ್ಟ್ರಿಂಗ್ಗಳನ್ನು ಹೊಂದಿರಬೇಕು ಎಂದು ಗಮನಿಸಲಾಗಿದೆ. ಅಲ್ಗಾರಿದಮ್ಗೆ ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ ಹೋಲಿಕೆಗಳು ಮತ್ತು ಸ್ಥಿರ ಸ್ಥಳಾವಕಾಶ ಮಾತ್ರ ಬೇಕಾಗುತ್ತದೆ. ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಎರಡು ಹಂತಗಳಾಗಿ ವಿಂಗಡಿಸಲಾಗಿದೆ. ಮೊದಲ ಹಂತವು ತ್ವರಿತ ಜರಡಿಯಾಗಿದ್ದು, ಇದು ಲೆಕ್ಸಿಕೋಗ್ರಾಫಿಕಲ್ ಕನಿಷ್ಠ ತಿರುಗುವಿಕೆಗೆ ಆರಂಭಿಕ ಸ್ಥಳಗಳಲ್ಲದ ಸೂಚ್ಯಂಕಗಳನ್ನು ತಳ್ಳಿಹಾಕುತ್ತದೆ. ಎರಡನೇ ಹಂತವು ನಂತರ ಉಳಿದಿರುವ ಸೂಚ್ಯಂಕಗಳಿಂದ ನಿಘಂಟಿನ ಕನಿಷ್ಠ ತಿರುಗುವಿಕೆಯ ಆರಂಭಿಕ ಸೂಚ್ಯಂಕವನ್ನು ಕಂಡುಕೊಳ್ಳುತ್ತದೆ. ದುವಾಲ್ನ ಲಿಂಡನ್ ಫ್ಯಾಕ್ಟರೈಸೇಶನ್ ಅಲ್ಗಾರಿದಮ್ ದುವಾಲ್ (1983) ಅದರ ಘಟಕ ಲಿಂಡನ್ ಪದಗಳಲ್ಲಿ ಸ್ಟ್ರಿಂಗ್ನ ಫ್ಯಾಕ್ಟರೈಸೇಶನ್ ಅನ್ನು ಒಳಗೊಂಡಿರುವ ಪರಿಣಾಮಕಾರಿ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತಾಪಿಸಿತು, ಇದು ಸ್ಥಿರವಾದ ಮೆಮೊರಿ ಅವಶ್ಯಕತೆಯೊಂದಿಗೆ ರೇಖೀಯ ಸಮಯದಲ್ಲಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ. ರೂಪಾಂತರಗಳು ಶಿಲೋಚ್ (1979) ಸಾಮಾನ್ಯೀಕರಣದ ಅವಶ್ಯಕತೆಯಿಲ್ಲದೆ ಸಮಾನತೆಗಾಗಿ ಎರಡು ವೃತ್ತಾಕಾರದ ತಂತಿಗಳನ್ನು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಹೋಲಿಸಲು ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತಾಪಿಸಿದರು. ಅಲ್ಗಾರಿದಮ್ನಿಂದ ಉಂಟಾಗುವ ಹೆಚ್ಚುವರಿ ಅನ್ವಯವೆಂದರೆ ಪುನರಾವರ್ತನೆಗಳಿಲ್ಲದೆ ಕೆಲವು ರಾಸಾಯನಿಕ ರಚನೆಗಳ ವೇಗದ ಉತ್ಪಾದನೆಯಾಗಿದೆ. ಲಿಂಡನ್ ಪದ ಕ್ನುತ್-ಮೋರಿಸ್-ಪ್ರ್ಯಾಟ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಸಹ ನೋಡಿ ಉಲ್ಲೇಖಗಳು ತಂತಿಗಳ ಮೇಲಿನ ಸಮಸ್ಯೆಗಳು ಲೆಕ್ಸಿಕೋಗ್ರಫಿ ಉದಾಹರಣೆ ಕೋಡ್ನೊಂದಿಗೆ ಲೇಖನಗಳು