در این قسمت تیم کدگیت را با آموزش جستجوی Naive در جاوا همراهی کنید. ابتدا توضیح کوتاهی در مورد نحوه کار با الگوریتم را می‌دهیم سپس به پیاده سازی این الگوریتم در جاوا پرداخته و در آخر به بررسی خروجی الگوریتم خواهیم پرداخت. همچنین پیشنهاد می‌کنیم قبل از مطالعه این جلسه، آموزش‌های زیر را مطالعه کنید:
جستجوی Naive در جاوا
الگوریتم جستجوی رشته (و یا تطبیق رشته‌ها) به رده مهمی از الگوریتم‌های موجود در رابطه با رشته‌ها اطلاق می‌شود. همانطور که از عنوانشان مشخص است، برای پیدا کردن یک رشته در میان یک متن بکار می‌روند و مکان آن رشته بخصوص را در متن مشخص می‌کنند و همچنین کاربرد بسیاری از جمله در جستجوهای اینترنتی دارند(ویکیپدیا).
الگوریتم جستجوی Naive در یک متن به جستجوی رشته‌‌ی ورودی(رشته‌ای خاص) می‌گردد. اگر رشته درون متن پیدا شد یا اصطلاحا تطابق پیدا شد محل تطابق چاپ و یک خانه به جلو رفته و دوباره جستجوی تطابق درون متن را ادامه می‌دهد.
پیاده سازی الگوریتم جستجوی Naive در جاوا
برای پیاده سازی الگوریتم Naive در جاوا ابتدا دو رشته به نام Text و Pattern داریم که درون آرایه می‌ریزیم. حال باید درون Text به دنبال Pattern بگردیم. برای این کار کافی است تک تک خانه های آرایه Text را رفته و در صورت یافتن Pattern آن را چاپ و به خانه بعدی می‌رویم. تصویر زیر نمایانگر بهتری از روش الگوریتم است:
کد این الگوریتم بسیار ساده می‌باشد. ابتدا کد را ببینید تا توضیحی در مورد آن داده شود:
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
اندیس‌هایی که در آن الگوی ما پیدا می‌شود درون خروجی چاپ می‌کنیم.
