الگوریتم مرز یک واژه و کاربرد آن در به دست آوردن الگوریتم تداخل واژه ها

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