وظيفة في C ++ للعثور على ما إذا كانت كلمة ما هي بادئة

Question

دعني أن لدي بعض الكلمات AB ، AAB ، AA.

AB ليس بادئة لـ AAB ولكن AA هي بادئة لـ AAB لأنه إذا قمت فقط بإضافة B في نهاية AA ، فسيصبح AAB ، وهو أمر غير ممكن مع AB.

لذلك ، هل هناك أي وظيفة في C ++ (STL) حتى أتمكن من تحديد كلمتين إذا كانت إحداها بادئة للآخر؟

شكرًا.

Answer 1

template<class C, class T, class A>
bool starts_with(std::basic_string<C,T,A> const& haystack,
                 std::basic_string<C,T,A> const& needle)
{
  return needle.length() <= haystack.length() &&
    std::equal(needle.begin(), needle.end(), haystack.begin());
}

لاحظ أن فحص الطول ليس تحسينًا سابقًا لأوانه ، فمن المطلوب تلبية الشروط المسبقة لـ STD :: Equal.

Answer 2

std::string full = "AAB", pre= "AA";
bool prefixed = full.find( pre ) == 0;

أو ماذا عن:

bool prefixed =  full.compare( 0, pre.size(), pre ) == 0;

Answer 3

std::string full = "AAB", lookfor = "AA";
const bool isprefixmatch = (full.substr(0,lookfor.lenght())==lookfor);

Answer 4

تعمل هذه الإجابة مع C و C ++ ولا تتطلب STL.

// test if string2 a prefix of string1
// inputs must be non NULL
// returns TRUE if string2 is a prefix, otherwise FALSE

int isAPrefix(const char *string1,
              const char *string2)
{
    return (strncmp(string1, string2, strlen(string2)) == 0);
}

Answer 5

إذا كنت تعتمد بالفعل على التعزيز ، فهناك boost::algorithm::starts_with.

int main()
{
    std::cout << boost::algorithm::starts_with("abba", "ab"); // true
    std::cout << boost::algorithm::starts_with("abba", "ba"); // false
    return 0;
}

كلما وجدت std::string يفتقر إلى طريقة معالجة السلسلة التي تحتاجها ، تحقق من زيادة خوارزميات سلسلة مكتبة.

Answer 6

استخدم ال find طريقة سلسلة. تحقق مما إذا كان الفهرس الذي يعود هو في بداية السلسلة.

Answer 7

http://www.cplusplus.com/reference/string/string/ هو مكان جيد للبحث عن أشياء مثل هذه. يستغرق 10 دقائق للتعرف على هذه الوظائف ، لأن معظمها مفيد للغاية.

يمكنك استخدام البحث للعثور على النص في أي مكان في السلسلة الأخرى ، ولكن قد يكون Find_first_of أكثر ملاءمة (ومقارنة مع اللاحقة). خلاف ذلك للعثور على اللاحقة ، سيكون Find_last_of مناسبًا.

Answer 8

أعتقد أن الإجابة الحقيقية لمشكلتك هي استخدام شجرة بادئة. ستقوم خوارزمية الإجابات المقبولة بالمهمة ، ولكن سيتعين عليك التحقق من كلمة البادئة الخاصة بك إلى كل كلمة أخرى في مجموعة الكلمات الخاصة بك والتي تكون خطية في الوقت المناسب. افعل ذلك لجميع الكلمات (قل أنك تريد الحصول على كل الكلمات التي هي بادئات بكلمات أخرى) ولديك التعقيد O (n^2) على يديك. التحقق البسيط ما إذا كانت الكلمة هي بادئة لآخر خطي على طول الكلمة.

سيجيب باستخدام شجرة بادئة على سؤالك الأول في الوقت اللوغاريتمي والثاني - في الخطي. إن التحقق مما إذا كانت الكلمة هي بادئة مجرد نزهة لأسفل من الجذر لأعلى حتى تجد الكلمة الموجودة في الشجرة وأن العقدة الأخيرة ليست ورقة (بمعنى كلمة أطول تمتد) - محدودة في ارتفاع الشجرة. اجتياز الشجرة ، من ناحية أخرى ، وكتابة الكلمة الحالية في كل خطوة لا تكون فيها العقدة الأخيرة ليست ورقة من شأنها أن تسفر عن قائمة بجميع كلمات البادئة. يتم اجتياز الشجرة في الوقت الخطي حيث ستقوم بزيارة كل عقدة مرة واحدة فقط.

Answer 9

إذا اكتشفت فقط سلسلة أو سلسلة فرعية ، فستكون بادئة بخلاف u يمكن ببساطة استخدام هذه fn

 std::size_t found = str1.find(str2); //returns position of str2 in str1 (if found==0) than it is prefix else not.

إذا لم يكن موجودًا مما يعيد قيمة القمامة وإذا كنت تفعل الشيء نفسه من أجل لا. من الأوتار وأريد أن تفعل بطريقة سريعة عليك استخدام تري.