java, جاوا, ساختمان داده در جاوا

الگوریتم جستجوی Naive در جاوا یا Naive Pattern Searching

الگوریتم جستجوی Naive در جاوا

در این قسمت تیم کدگیت را با آموزش جستجوی Naive در جاوا همراهی کنید. ابتدا توضیح کوتاهی در مورد نحوه کار با الگوریتم را می‌دهیم سپس به پیاده سازی این الگوریتم در جاوا پرداخته و در آخر به بررسی خروجی الگوریتم خواهیم پرداخت. همچنین پیشنهاد می‌کنیم قبل از مطالعه این جلسه، آموزش‌های زیر را مطالعه کنید:

  1. حلقه For در جاوا
  2. متد در جاوا
  3. if در جاوا
  4. آرایه در جاوا
  5. رشته ها در جاوا

جستجوی Naive در جاوا

الگوریتم جستجوی رشته (و یا تطبیق رشته‌ها) به رده مهمی از الگوریتم‌های موجود در رابطه با رشته‌ها اطلاق می‌شود. همانطور که از عنوانشان مشخص است، برای پیدا کردن یک رشته در میان یک متن بکار می‌روند و مکان آن رشته بخصوص را در متن مشخص می‌کنند و همچنین کاربرد بسیاری از جمله در جستجوهای اینترنتی دارند(ویکیپدیا).

الگوریتم جستجوی Naive در یک متن به جستجوی رشته‌‌ی ورودی(رشته‌ای خاص) می‌گردد. اگر رشته درون متن پیدا شد یا اصطلاحا تطابق پیدا شد محل تطابق چاپ و یک خانه به جلو رفته و دوباره جستجوی تطابق درون متن را ادامه می‌دهد.

الگوریتم جستجوی Naive

پیاده سازی الگوریتم جستجوی Naive در جاوا

برای پیاده سازی الگوریتم Naive در جاوا ابتدا دو رشته به نام Text و Pattern داریم که درون آرایه می‌ریزیم. حال باید درون Text به دنبال Pattern بگردیم. برای این کار کافی است تک تک خانه های آرایه Text را رفته و در صورت یافتن Pattern آن را چاپ و به خانه بعدی می‌رویم. تصویر زیر نمایانگر بهتری از روش الگوریتم است:

الگوریتم جستجوی Naive

کد این الگوریتم بسیار ساده می‌باشد. ابتدا کد را ببینید تا توضیحی در مورد آن داده شود:

public class NaiveSearch {



    public static void search(String txt, String pat)

    {

        int M = pat.length();

        int N = txt.length();



        for (int i = 0; i <= N - M; i++) {



            int j;



            for (j = 0; j < M; j++)

                if (txt.charAt(i + j) != pat.charAt(j))

                    break;



            if (j == M)

                System.out.println("Pattern found at index " + i);

        }

    }



    public static void main(String[] args)

    {

        String txt = "AABAACAADAABAAABAA";

        String pat = "AABA";

        search(txt, pat);

    }

}

همانطور که در کد بالا می‌بینید دو حلقه For تو در تو نوشته شده که اولی برای بررسی و چرخش خانه‌های متغیر txt (همان متن ما) و دومین آرایه برای چرخش بر روی آرایه Pat (همان الگو برای یافتن در رشته) می‌باشد. درون حلقه دوم به بررسی تطابق متن و رشته‌ای که به دنبال آن می‌گردیم، می‌پردازیم (if درون حلقه دوم این کار را انجام می‌دهد). در آخر یک Main نوشته‌ایم و متد خود را با دادن دو رشته Txt و Pattern اجرا می‌کنیم. خروجی کد به صورت زیر می‌باشد:

Pattern found at index 9

Pattern found at index 13

اندیس‌هایی که در آن الگوی ما پیدا می‌شود درون خروجی چاپ می‌کنیم.

پسورد: www.codegate.ir

نوشته های مشابه

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *