מציאת פולינדרום

[amir y]

מציאת פולינדרום

כתבתי משהו פשוט למציאת פולינדרום בתוך מחרוזת. הבעיה היא שיש לי מחרוזת ענקית (!!!) וזה לוקח המון המון זמן. יש למישהו רעיונות? (אני עשיתי 2 for-ים, שבודקים את כל האפשרויות).

 

[neko]

אתה חולה נפש, למה לבדוק את כל

האפשרויות? תתחיל להשוות את הסימן הראשון לאחרון, ותתקדם כלפי פנים...

 

[amir y]

לזה התכוונתי...

אני משווה קודם את הראשון והאחרון. אם זה לא פולינדרום, אז אני מפחית מהאחרון. אחרי זה מוסיף לראשון ולאחרון. אחרי זה מפחית מהראשון אחד ושניים מהאחרון... וכו וכו וכו ... אבל זה עדיין איטי ! יש עוד רעיונות?

 

[Metheny]

למה?

1. אם הגעת למילה בעלת אות אחת, סיימת (וזה פולינדרום). 2. אתה משווה את האות הראשונה לאחרונה 3. אם הם שוות, אתה מוריד אותם, וחוזר לשלב 1. אחרת, אתה מפסיק את הבדיקה (המילה היא לא פולינדרום)

 

[גיל14]

כתוב את זה באסמבלי...

או לחילופין תשכיר מהמוסד מחשב על.

 

[yair24]

יש כל מיני אלגוריתמים

למציאת פולינדרומים בזמנים יותר יעילים. אני כבר לא זוכר אם זה פולינדרום גנטי... הדבר היחיד שאני זוכר זה שיש אלגוריתם שנקרא RABIN KARP או משהו דומה... תחפש בגוגל אולי תמצא

 

[אוֹריארד]

../images/Emo5.gifאבל אבל אבל... ../images/Emo26.gif

אני לא כל-כך עוקב... יש לך שתי דרכים - עם רקורסיה ובלי. עם רקורסיה - כבר אמרו לך:

תנאי עצירה: אם המחרוזת באורך קטן מ-2 - אז מדובר בפולינדרום.

צעד: אם התו הראשון והאחרון שונים - תחזיר תשובה שלילית - אחרת תעיף את התווים הנ"ל וקרא שוב לפונקציה עם המחרוזת המקוצרת. בלי רקורסיה:

אתה צריך לולאה עם מספר איטרציות של אורך המחרוזת חלקי שתיים (ערך תחתון אם האורך לא זוגי).

אם נניח הלולאה מתחילה את הריצה מ-1, אז הלולאה בודקת בכל איטרציה אם התו ה-i והתו ה-(len-i+1) זהים. אם לא - מחזירה תשובה שלילית. אם הלולאה סיימה את פעולתה - מחזירה תשובה חיובית.

אם אין לך פונקציה למציאת אורך המחרוזת - תצטרך למצוא אותו לבד עם איזה while שרץ על המחרוזת. בכל מקרה הסיבוכיות תהיה O של n - כש-n הוא אורך המחרוזת, לא יותר.

 

[amir y]

שוב... ../images/Emo5.gif

אני מחפש פולינדרום בתוך מחרוזת. למשל: עבור המחרוזת "abcedbbde" הפולינדרום יהיה "edbbde", כי הוא הגדול ביותר. כך שלהוריד את התו האחרון והראשון זה לא רעיון כ"כ טוב...

 

[אוֹריארד]

אההה..... הבנתי אותך.. ../images/Emo26.gif

לא לא - הפתרון שהבאתי לך הוא לפונקציה שאומרת אם מחרוזת נתונה היא פולינדרום או לא. צודק. לגבי הבעיה שהצגת - נראה לי שהפתרון הנאיבי הבא יעבוד טוב:

מעבר אחד על המחרוזת בודק אחד משני מקרים: או שהוא מוצא תת-מחרוזת מהצורה "XX" (כלומר עם שני תווים זהים) או מהצורה "XYX" (כלומר 3 תווים כשהראשון והשלישי זהים).

לכל תת-מחרוזת כזו שהוא מוצא, הוא נכנס ללולאה שבכל איטרציה בודקת אם שני התווים הבאים גם זהים (כלומר אם "ZXYXZ" ואז "WZXYXZW" וכו') - ברגע שהם שונים היא מפסיקה.

המחרוזת הארוכה ביותר שנמצאה היא הפתרון. הפתרון הזה הוא אומנם O של n בריבוע (השלב הראשון הוא O של n - ולכל מחרוזת שנמצאה - מתבצע השלב השני שגם הוא O של n), אבל בפועל הוא יהיה זריז יותר מרוב הפתרונות הנאיבים שתיקח... אם הבנתי נכון - הפתרון שלך הוא O של n בשלישית (מעבר על כל האפשרויות זה O של n בריבוע, כפול בדיקה שזה O של n) - ככה שבכל מקרה זה יצא לך יותר יעיל.

 

[tkop]

אני חושב שאפשר ב-NLOGN

הרעיון לקוח מ=Patttern Matching. תעשה משהו דומה לקונבלוציה בין הטקסט לעצמו, כאשר בכל מקום שיש תווים שווים תקבל 1, כאשר הם שונים תקבל 0 (במקום פעולת הכפל בין שני תווים). תסתכל על מה שמתקבל, אם קצת משחקים אולי תוכל למצוא.

 

[tkop]

תיקון טעות

התבלבלתי עם רעיון אחר. מה שצריך לעשות זה לבנות עץ סיפות (Suffix tree) לטקסט, וגם לטקסט ההפוך, ולאחר מכן ניתן למצוא את הפולינדרום ב-NLOGNץ אם אתה רוצה, אתן קישור למאמר בנושא.

 

[Mapisto]

דעתי

תחפש אות שחוזרת על עצמה פעמיים בלבד. ותלך כלפי פנים לראות אם זה פולינדרום.

 

[tkop]

לא טוב

זה לא בודק את כל המקרים. לדוגמא -מחרוזת בינארית, קרוב לוודאי שלא יעבוד!!

 

[Mapisto]

הממ

תבדוק קוד אסקי של הראשון ותתחיל לחפש אם הוא חוזר.

 

[tkop]

ואם הוא חוזר

אז מה תעשה?

 

[Mapisto]

תלך בלולאה כלפי פנים

כדי לבדוק מחזוריות. עדיף מחסנית במחשבה שניה.

 

[tkop]

אבל

מחפשים פולינדרום מקסימלי בטקסט. לא כלשהן בכל מקרה - זה ב-N בשלישית

 

[אוֹריארד]

למה N בשלישית??....../images/Emo26.gif

למה לא N בשניה? הפתרון שהבאתי קודם זה N בשניה... (או שהפתרון מוטעה או הסיבוכיות שהבאתי מוטעית...) בכל מקרה - פונקציה שמקבלת אינדקס במחרוזת, ובודקת תו-תו (כלפי חוץ) האם זה פולינדרום - הסיבוכיות שלה לינארית (כי בכל איטרציה היא בודקת תו - והיא בודקת לכל היותר N תווים). ואם אתה מפעיל את הפונקציה הנ"ל לכל תו במחרוזת (כלומר N פעמים) - אתה מכסה את כל האפשרויות: סה"כ O של N בריבוע...

 

[אינגולמו]

רעיון

נסה את האלגוריתם הבא: השתמש במשהו שמזכיר מחסנית, אבל מתנהג גם כמו ווקטור, כלומר נותן גישה לכל איבריו מבלי להוציא איברים מהמבנה. בנוסף, השתמש ברשימה מקושרת של תורים דו-כיוונים (תראה בהמשך) כל תור דו כיווני שומר את אורכו. הרשימה שומרת מצביע לתור המקסימלי שהוכנס אליה. עבור כל איבר במחרוזת: 1. אם הוא זהה לאיבר בראש המחסנית, הוצא את שניהם ודחוף אותם לתור דו כיווני חדש (אחד מימין ואחד משמאל). מקרה קצה: אולי צריך להסתכל באיבר *שלפני* ראש המחסנית, במידה ומדובר בפלינדרום באורך איזוגי. 2. כל עוד ישנם איברים זהים בקלט ובראש המחסנית, הוסף אותם לאותו תור דו כיווני באותה הצורה. ברגע שהקלט שונה מראש המחסנית, עבור לתור דו כיווני חדש. כאשר נגמר הקלט: הדפס את התור המקסימלי שאותו "זוכרת" הרשימה המקושרת.

 

[אינגולמו]

דרך אגב

אם לא היה ברור: כל תור דו כיווני מחזיק פלינדרום יחיד, שנמצא במחרוזת. על זה מבוסס כל הרעיון. בנוסף, המחסנית עוזרת למצוא כל הפלינדרום *מבלי* לדעת את סופו מצד ימין, כלומר מבלי לעבור משני הכיוונים של המחזורת. ברגע שאתה מאכסן את כל הפלינדרומים ברשימה, והיא יודעת מי הארוך ביותר, סיימת. והיעילות היא כמובן לינארית.