איך אני מחפש מחרוזת במחזורת אחרת בC++

[tavor21]

אבל לא לחפש תו -תו...

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

תודהה לכל העוניםם ...

[MB]

ב- C יש לך את strstr שנמצאת ב- string.h

ב- C++ יש לך את find שהוא חלק מה- Class:

string

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

[Ghosthunter]

יש מספר אלגוריתמים שלא מחייבים אותך לרוץ על כל המחרוזת, אלא רק על חלק ממנה. הם קצת מסובכים יותר מהשיטה הרגילה.

באיזו מסגרת אתה צריך לממש את זה?

[tavor21]

קורס באוניברסיטה .... ,

[Ghosthunter]

זה קורס מבוא, אלגוריתמים או קורס תכנות OO?

ביקשו מיכם ליצור פונ שלא תעבור איבר איבר?

[Zelig]

יש לא מעט אלגוריתמים יעילים לחיפוש מחרוזות, אבל השאלה היא האם צריך את זה יעיל (לדוגמא לצורך פרוייקט ברשתות מחשבים) או שצריך את זה פשוט (לצורך תרגיל בית בסיסי). אם צריך משהו פשוט אז תשתמש ב-strstr או ב-find.

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

KMP (Knuth-Moris-Pratt) הוא אלגוריתם פשוט יחסית (קל להבנה ומימוש) אך יעיל, ומבוסס על הכנת טבלה המתארת את המחרוזת שאותה מחפשים. יש לו סיבוכיות של O(n) כאשר N הוא אורך המחרוזת בה מחפשים. סיבוכיות הכנת הטבלה מראש היא O(m) כאשר M הוא אורך תת-המחרוזת שאותה מחפשים.

Boyer-Moore (BM) הוא אלגוריתם אחר המיועד לחיפוש מחרוזות, וגם הוא מבוסס על טבלאות.

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

Karp-Rabin מבוסס על השוואת Hash של חלקים מהמחרוזת ל-hash של התת-מחרוזת.