שאלה על מחרוזות

[udist]

אני צריך למצוא אלגוריתם יעיל ככל הניתן (לינארי) אשר הקלט שלו זה מחרוזת S

והפלט שלו הוא תת מחרוזת T של S כך שאם נשרשר את T לעצמה n פעמים, כלומר T^n

נקבל את המחרוזת S בתחילת T^n, כלומר S היא רישא של T^n.

[Gil28]

לא הבנתי. אתה יכול לתת דוגמא?

[udist]

כן, לדוגמא עבור קלט S=1212

הפתרון הוא T=12

מכיוון שאם נשרשר את T לעצמה מספיק פעמים נקבל

T^n=121212121212...

ונשים לב שS היא רישא של T^n

(כמובן שצריך למצוא T מינימאל)

[Gil28]

כלומר אתה אמור למצוא האם S מחזורית ואם כן מה המחזור שלה.

[HorseCalledWar]

צור את המחרוזות T ו-Q ושים בהן את התו הראשון של S.

עבור עם I (משתנה מספרי) על מחרוזת S:

- הוסף ל-Q את התו במיקום I במחרוזת S.

- אם התו במיקום I ב-S שווה לתו ה-I%L (כש-L הוא האורך של T) במחרוזת T,

--הגדר את T כ-Q (בלי references, הכל by value).

או בקוד C# אם תרצה:

static string Check(string s)
   {
     string t = s[0].ToString(), q = s[0].ToString();

     for (int i = 1; i < s.Length; i++)
     {
      q += s[i];
      if (t[i % t.Length] != s[i])
        t = q;
     }

     return t;
   }

[udist]

כלומר אתה אמור למצוא האם S מחזורית ואם כן מה המחזור שלה.

כן.

דוג' נגדית לאלגוריתם שנתנו פה:

S = 1211212

המחרוזת אותה יחזיר האלגוריתם היא כל S בעוד התשובה היא:

12112

עוד פתרונות?

[Gil28]

לפי הדוגמא שלך התשובה לשאלה שלי היא לא.

[HorseCalledWar]

צודק, האלגוריתם שהבאתי חושב על סוף S כעל ההתחלה של T. במצב כזה, פשוט להוסיף שורה שבודקת האם האורך של S חלקי T שווה לאפס לפני ה-return.

if (s.Length / t.Length != 0) return s;

[udist]

לפי הדוגמא שלך התשובה לשאלה שלי היא לא.

כן ולא. זה שרואים רק חלק מהמחזור, לא אומר שS לא מחזורית, אלא שהמחזור שלה גדול מאורך חצי המחרוזת..

אבל העיקר שהבנת למה הכוונה מהדוגמה.

HorseCalledWar

לא הבנתי את התיקון לאלגוריתם...

[Maor_Splinter]

הרעיון הבסיסי באלגוריתם ש-HorseCalledWar כתב הוא נכון.

עוברים על S ותוך כדיי בונים את T:

כל עוד ניתן לשבץ את T על S בצורה החוקית (תחשוב כאילו אתה מנסה "לרצף" את S בחתיכות של T-ים) ממשיכים;

ברגע שהגענו למצב שזה לא ניתן, נשרשר לT את תת המחרוזת P שמתחילה בנקודה האחרונה שבה ביצענו את פעולת השרשור מS עד למקום הנוכחי שהגענו אליו בS.