Palindrome tree
ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನದಲ್ಲಿ ಈರ್ಟ್ರೀ ಎಂದೂ ಕರೆಯಲಾಗುವ ಪಾಲಿಂಡ್ರೋಮ್ ಮರವು ಒಂದು ರೀತಿಯ ಸರ್ಚ್ ಟ್ರೀ ಆಗಿದ್ದು, ಇದು ಸ್ಟ್ರಿಂಗ್ನಲ್ಲಿರುವ ಎಲ್ಲಾ ಪಾಲಿಂಡ್ರೋಮ್ಗಳಿಗೆ ತ್ವರಿತ ಪ್ರವೇಶವನ್ನು ನೀಡುತ್ತದೆ. ಅವುಗಳನ್ನು ಉದ್ದವಾದ ಪಾಲಿಂಡ್ರೋಮಿಕ್ ಸಬ್ಸ್ಟ್ರಿಂಗ್, ಕೆ-ಫ್ಯಾಕ್ಟರೈಸೇಶನ್ ಸಮಸ್ಯೆ (ನಿರ್ದಿಷ್ಟ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ನಿಖರವಾಗಿ ಕೆ ಪಾಲಿಂಡ್ರೋಮ್ಗಳಾಗಿ ವಿಂಗಡಿಸಬಹುದು), ಸ್ಟ್ರಿಂಗ್ನ ಪಾಲಿಂಡ್ರೋಮಿಕ್ ಉದ್ದ (ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ನಿರ್ಮಿಸಲು ಅಗತ್ಯವಿರುವ ಕನಿಷ್ಠ ಸಂಖ್ಯೆಯ ಪಾಲಿಂಡ್ರೋಮ್ಗಳು), ಮತ್ತು ಎಲ್ಲಾ ವಿಭಿನ್ನ ಉಪ-ಪಾಲಿಂಡ್ರೋಮ್ಗಳನ್ನು ಕಂಡುಹಿಡಿಯಲು ಮತ್ತು ಎಣಿಸಲು ಬಳಸಬಹುದು. ಪಾಲಿಂಡ್ರೋಮ್ ಮರಗಳು ಇದನ್ನು ಆನ್ಲೈನ್ ರೀತಿಯಲ್ಲಿ ಮಾಡುತ್ತವೆ, ಅಂದರೆ ಇದಕ್ಕೆ ಆರಂಭದಲ್ಲಿ ಸಂಪೂರ್ಣ ಸ್ಟ್ರಿಂಗ್ ಅಗತ್ಯವಿಲ್ಲ ಮತ್ತು ಅಕ್ಷರದಿಂದ ಅಕ್ಷರಕ್ಕೆ ಸೇರಿಸಬಹುದು. ವಿವರಣೆ ಹೆಚ್ಚಿನ ಮರಗಳಂತೆ, ಪಾಲಿಂಡ್ರೋಮ್ ಮರವು ಶೃಂಗಗಳು ಮತ್ತು ನಿರ್ದೇಶನದ ಅಂಚುಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಮರದ ಪ್ರತಿಯೊಂದು ಶೃಂಗವು ಪಾಲಿಂಡ್ರೋಮ್ ಅನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ (ಉದಾ. 'ಟ್ಯಾಕೋಕ್ಯಾಟ್') ಆದರೆ ಪಾಲಿಂಡ್ರೋಮ್ನ ಉದ್ದವನ್ನು ಮಾತ್ರ ಸಂಗ್ರಹಿಸುತ್ತದೆ, ಮತ್ತು ಪ್ರತಿ ಅಂಚು ಒಂದು ಅಕ್ಷರ ಅಥವಾ ಪ್ರತ್ಯಯವನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ. ಅಕ್ಷರದ ಅಂಚುಗಳು ಮೂಲ ಶೃಂಗದಿಂದ ಪ್ರತಿನಿಧಿಸಲಾದ ಪಾಲಿಂಡ್ರೋಮ್ನ ಎರಡೂ ತುದಿಗಳಿಗೆ ಅಕ್ಷರವನ್ನು ಸೇರಿಸಿದಾಗ, ಗಮ್ಯಸ್ಥಾನದ ಶೃಂಗದಲ್ಲಿ ಪಾಲಿಂಡ್ರೋಮ್ ಅನ್ನು ರಚಿಸಲಾಗುತ್ತದೆ (ಉದಾಹರಣೆಗೆ. 'ಟಿ' ಎಂದು ಲೇಬಲ್ ಮಾಡಲಾದ ಅಂಚು ಮೂಲ ಶೃಂಗ 'ಅಕೋಕಾ' ಅನ್ನು ಗಮ್ಯಸ್ಥಾನದ ಶೃಂಗ 'ಟಕೋಕ್ಯಾಟ್' ಗೆ ಸಂಪರ್ಕಿಸುತ್ತದೆ). ಪ್ರತ್ಯಯದ ತುದಿಯು ಪ್ರತಿ ಪಾಲಿಂಡ್ರೋಮ್ ಅನ್ನು ಅದು ಹೊಂದಿರುವ ಅತಿದೊಡ್ಡ ಪಾಲಿಂಡ್ರೋಮ್ ಪ್ರತ್ಯಯಕ್ಕೆ ಸಂಪರ್ಕಿಸುತ್ತದೆ (ಹಿಂದಿನ ಉದಾಹರಣೆಯಲ್ಲಿ 'ಟ್ಯಾಕೊಕ್ಯಾಟ್' ಪ್ರತ್ಯಯದ ತುದಿಯನ್ನು 'ಟಿ' ಗೆ ಹೊಂದಿರುತ್ತದೆ ಮತ್ತು 'ಅಟಾಕೊಕಾಟಾ' ಪ್ರತ್ಯಯವು 'ಅಟಾ' ಗೆ ಸಂಪರ್ಕವನ್ನು ಹೊಂದಿರುತ್ತದೆ). ಪಾಲಿಂಡ್ರೋಮ್ ಮರಗಳು ಸಾಮಾನ್ಯ ಮರಗಳಿಗಿಂತ ಭಿನ್ನವಾಗಿದ್ದರೆ, ಅವು ಎರಡು ಬೇರುಗಳನ್ನು ಹೊಂದಿರುತ್ತವೆ (ಏಕೆಂದರೆ ಅವು ವಾಸ್ತವವಾಗಿ ಎರಡು ಪ್ರತ್ಯೇಕ ಮರಗಳಾಗಿವೆ). ಎರಡು ಬೇರುಗಳು −1, ಮತ್ತು 0 ಉದ್ದದ ಪಾಲಿಂಡ್ರೋಮ್ಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತವೆ. ಅಂದರೆ, 'ಎ' ಅಕ್ಷರವನ್ನು ಎರಡೂ ಬೇರುಗಳಿಗೆ ಸೇರಿಸಿದರೆ ಮರವು ಅನುಕ್ರಮವಾಗಿ 'ಎ' ಮತ್ತು 'ಆ' ಅನ್ನು ಉತ್ಪಾದಿಸುತ್ತದೆ. ಪ್ರತಿ ಅಂಚು ಸಮ ಸಂಖ್ಯೆಯ ಅಕ್ಷರಗಳನ್ನು ಸೇರಿಸುವುದರಿಂದ (ಅಥವಾ ತೆಗೆದುಹಾಕುವುದರಿಂದ), ಎರಡು ಮರಗಳು ಯಾವಾಗಲೂ ಪ್ರತ್ಯಯದ ಅಂಚುಗಳಿಂದ ಮಾತ್ರ ಸಂಪರ್ಕ ಹೊಂದಿರುತ್ತವೆ. ಪಾಲಿಂಡ್ರೋಮ್ ಮರವು ಆನ್ಲೈನ್ ನಿರ್ಮಾಣವನ್ನು ಅನುಸರಿಸುವುದರಿಂದ, ಅದು ಮರಕ್ಕೆ ಸೇರಿಸಲಾದ ಕೊನೆಯ ಪಾಲಿಂಡ್ರೋಮ್ಗೆ ಪಾಯಿಂಟರ್ ಅನ್ನು ನಿರ್ವಹಿಸುತ್ತದೆ. ಪ್ಯಾಲಿಂಡ್ರೋಮ್ ಮರಕ್ಕೆ ಮುಂದಿನ ಅಕ್ಷರವನ್ನು ಸೇರಿಸಲು, ಪ್ಯಾಲಿಂಡ್ರೋಮ್ಗೆ ಮುಂಚಿನ ಮೊದಲ ಅಕ್ಷರವು ಸೇರಿಸಲಾಗುತ್ತಿರುವ ಅಕ್ಷರಕ್ಕೆ ಹೊಂದಿಕೆಯಾಗುತ್ತದೆಯೇ ಎಂದು ಮೊದಲು ಪರಿಶೀಲಿಸಿ, ಇಲ್ಲದಿದ್ದರೆ, ಮರಕ್ಕೆ ಪ್ಯಾಲಿಂಡ್ರೋಮ್ ಅನ್ನು ಸೇರಿಸುವವರೆಗೆ ಪ್ರತ್ಯಯ ಕೊಂಡಿಗಳನ್ನು ಅನುಸರಿಸಲಾಗುತ್ತದೆ. ಒಮ್ಮೆ ಪಾಲಿಂಡ್ರೋಮ್ ಪತ್ತೆಯಾದರೆ, ಅದು ಈಗಾಗಲೇ ಮರದಲ್ಲಿ ಅಸ್ತಿತ್ವದಲ್ಲಿದ್ದರೆ, ಮಾಡಲು ಯಾವುದೇ ಕೆಲಸವಿಲ್ಲ. ಇಲ್ಲದಿದ್ದರೆ, ಪ್ರತ್ಯಯದಿಂದ ಹೊಸ ಶೃಂಗಕ್ಕೆ ಕೊಂಡಿಯೊಂದಿಗೆ ಹೊಸ ಶೃಂಗವನ್ನು ಸೇರಿಸಲಾಗುತ್ತದೆ ಮತ್ತು ಹೊಸ ಶೃಂಗಕ್ಕೆ ಪ್ರತ್ಯಯ ಕೊಂಡಿಯನ್ನು ಸೇರಿಸಲಾಗುತ್ತದೆ. ಹೊಸ ಪಾಲಿಂಡ್ರೋಮ್ನ ಉದ್ದವು 1 ಆಗಿದ್ದರೆ, ಪ್ರತ್ಯಯ ಕೊಂಡಿ-1 ಉದ್ದವನ್ನು ಪ್ರತಿನಿಧಿಸುವ ಪಾಲಿಂಡ್ರೋಮ್ ಮರದ ಮೂಲವನ್ನು ಸೂಚಿಸುತ್ತದೆ. #ಎಸ್-> ಇನ್ಪುಟ್ ಸ್ಟ್ರಿಂಗ್ #ಎಕ್ಸ್-> ಅಕ್ಷರದ ಸ್ಟ್ರಿಂಗ್ನಲ್ಲಿರುವ ಸ್ಥಾನವು ಡಿಫ್ ಆಡ್ (ಎಕ್ಸ್ಃ ಇಂಟ್)-> ಬೂಲ್ಃ "ಪಾಲಿಂಡ್ರೋಮ್ ಮರಕ್ಕೆ ಅಕ್ಷರವನ್ನು ಸೇರಿಸಿ". ಆದರೆ ನಿಜಃ x-1-current.length> = 0 ಆಗಿದ್ದರೆ ಮತ್ತು S [x-1-current.length] = = S [x] ಆಗಿದ್ದರೆಃ ಬ್ರೇಕ್ ಕರೆಂಟ್ = current.suffix ಆಗಿದ್ದರೆ current.add [S [x] ಯಾವುದೂ ಇಲ್ಲಃ ರಿಟರ್ನ್ ಫಾಲ್ಸ್ ಸಫಿಕ್ಸ್ = ಕರೆಂಟ್ ಕರೆಂಟ್ = ಪಾಲಿಂಡ್ರೋಮ್ _ ವೆರ್ಟೆಕ್ಸ್ () current.length = suffix.length + 2 suffix.add [S [x] = ಕರೆಂಟ್ ಆಗಿದ್ದರೆ current.length = = 1: current.suffix = ರೂಟ್ ಆಗಿದ್ದರೆ ಟ್ರೂಃ ಸಫಿಕ್ಸ್ = suffix.suffix ಆಗಿದ್ದರೆ x-1-suffix.length = 0 ಮತ್ತು S [x-suffix.length = = S [x]: current.suffix ಪ್ರತಿ ಶೃಂಗಕ್ಕೆ ಉದ್ದದ ಶ್ರೇಣಿಯನ್ನು ಸೇರಿಸುವ ಮೂಲಕ ಮತ್ತು ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಸೇರಿಸುವಾಗ ಆ ಶೃಂಗವನ್ನು ತಲುಪಿದರೆ ಸೂಚ್ಯಂಕದಲ್ಲಿ ಧ್ವಜವನ್ನು 1 ಕ್ಕೆ ಹೊಂದಿಸುವ ಮೂಲಕ ಇದನ್ನು ಸಾಧಿಸಲಾಗುತ್ತದೆ. ಪ್ರತಿ ಸ್ಟ್ರಿಂಗ್ನ ಅಂತ್ಯದಲ್ಲಿರುವ ಮೂಲಕ್ಕೆ ಪ್ರಸ್ತುತ ಪಾಯಿಂಟರ್ ಅನ್ನು ಮರುಹೊಂದಿಸುವುದು ಮಾತ್ರ ಅಗತ್ಯವಿರುವ ಇತರ ಮಾರ್ಪಾಡು. ಮರಗಳನ್ನು ಈ ರೀತಿ ಜೋಡಿಸುವ ಮೂಲಕ ಈ ಕೆಳಗಿನ ಸಮಸ್ಯೆಗಳನ್ನು ಪರಿಹರಿಸಬಹುದುಃ ಎಲ್ಲಾ ತಂತಿಗಳಿಗೆ ಸಾಮಾನ್ಯವಾದ ಪಾಲಿಂಡ್ರೋಮ್ಗಳ ಸಂಖ್ಯೆ ಒಂದು ತಂತಿಯಲ್ಲಿನ ವಿಶಿಷ್ಟವಾದ ಪಾಲಿಂಡ್ರೋಮ್ಗಳ ಸಂಖ್ಯೆ ಎಲ್ಲಾ ತಂತಿಗಳಿಗೆ ಸಾಮಾನ್ಯವಾದ ಅತಿ ಉದ್ದದ ಪಾಲಿಂಡ್ರೋಮ್ ಇತರರಿಗಿಂತ ಒಂದು ಸ್ಟ್ರಿಂಗ್ನಲ್ಲಿ ಹೆಚ್ಚಾಗಿ ಕಂಡುಬರುವ ಪಾಲಿಂಡ್ರೋಮ್ಗಳ ಸಂಖ್ಯೆ ಸಂಕೀರ್ಣತೆ ಪಾಲಿಂಡ್ರೋಮ್ ಮರವನ್ನು ನಿರ್ಮಿಸಲು ಸಮಯ ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ, ಅಲ್ಲಿ ಸ್ಟ್ರಿಂಗ್ನ ಉದ್ದ ಮತ್ತು ವರ್ಣಮಾಲೆಯ ಗಾತ್ರ. (x) ಅನ್ನು ಸೇರಿಸಲು ಕರೆಗಳೊಂದಿಗೆ, ಪ್ರತಿ ಕರೆಯು ಮರುಪಾವತಿ ಸಮಯವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ. ಇದು ಸೇರಿಸುವ ಪ್ರತಿ ಕರೆಯ ಫಲಿತಾಂಶವಾಗಿದೆ (x) ಪ್ರಸ್ತುತ ಶೃಂಗದ (ಮರದ ಕೊನೆಯ ಪಾಲಿಂಡ್ರೋಮ್) ಆಳವನ್ನು ಗರಿಷ್ಠ ಒಂದರಿಂದ ಹೆಚ್ಚಿಸುತ್ತದೆ, ಮತ್ತು ಶೃಂಗದ ಎಲ್ಲಾ ಅಕ್ಷರದ ಅಂಚುಗಳನ್ನು ಹುಡುಕಲು ಸಮಯ ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ. (x) ಅನ್ನು ಸೇರಿಸಲು ಪ್ರತಿ ಕರೆಗೆ ಮರವನ್ನು ಮೇಲಕ್ಕೆ ಮತ್ತು ಕೆಳಕ್ಕೆ ಚಲಿಸುವ ವೆಚ್ಚವನ್ನು ನಿಗದಿಪಡಿಸುವ ಮೂಲಕ, ಮರವನ್ನು ಮೇಲಕ್ಕೆ ಚಲಿಸುವಾಗ (x) ಅನ್ನು ಸೇರಿಸಲು ಒಂದೇ ಸಂಖ್ಯೆಯ ಕರೆಗಳ ಮೂಲಕ ಒಂದಕ್ಕಿಂತ ಹೆಚ್ಚು ಬಾರಿ ಮರವನ್ನು ಮೇಲಕ್ಕೆ ಚಲಿಸುವ ವೆಚ್ಚವನ್ನು 'ಪಾವತಿಸಲಾಗುತ್ತದೆ'. ಒಂದು ಪಾಲಿಂಡ್ರೋಮ್ ಮರವು ಜಾಗವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆಃ ಹೆಚ್ಚಿನ ಶೃಂಗಗಳಲ್ಲಿ ಉಪ-ಪಾಲಿಂಡ್ರೋಮ್ಗಳು ಮತ್ತು ಎರಡು ಬೇರುಗಳು, ಅಂಚುಗಳನ್ನು ಸಂಗ್ರಹಿಸಿ, ಶೃಂಗಗಳು ಮತ್ತು ಪ್ರತ್ಯಯ ಅಂಚುಗಳನ್ನು ಸಂಪರ್ಕಿಸುತ್ತದೆ. ಪ್ರತಿ ಪಾಲಿಂಡ್ರೋಮ್ಗೆ ಇರುವ ಆಡ್ ಅಂಚುಗಳನ್ನು ಮಾತ್ರ ಸಂಗ್ರಹಿಸುವ ಬದಲು ಉದ್ದದ ಅಂಚುಗಳ ಒಂದು ಶ್ರೇಣಿಯನ್ನು ಸಂಗ್ರಹಿಸಿದರೆ, ಸರಿಯಾದ ಅಂಚನ್ನು ಕಂಡುಹಿಡಿಯುವುದನ್ನು ನಿರ್ಮಾಣದ ಸಮಯವನ್ನು ಕಡಿಮೆ ಮಾಡುವ ಸ್ಥಿರ ಸಮಯದಲ್ಲಿ ಮಾಡಬಹುದು, ಜಾಗವನ್ನು ಹೆಚ್ಚಿಸುವಾಗ, ಪಾಲಿಂಡ್ರೋಮ್ಗಳ ಸಂಖ್ಯೆ ಎಲ್ಲಿದೆ. ಉಲ್ಲೇಖ ಮರಗಳು (ದತ್ತಾಂಶ ರಚನೆಗಳು)