একটি স্ট্রিং দেওয়া হয়েছে যেখানে আমাদের পরীক্ষা করতে হবে যে দীর্ঘতম উপসর্গের দৈর্ঘ্য যা স্ট্রিংয়ের একটি প্রত্যয়ও যেমন একটি স্ট্রিং "abcab" আছে তাই এখানে "ab" দৈর্ঘ্য 2 এবং একই উপসর্গ সহ দীর্ঘতম সাবস্ট্রিং এবং প্রত্যয়।
উদাহরণ
Input: str[] = { “aabbccdaabbcc” }
Output: 6
Input: abdab
Output: 2 যদি আমরা স্ট্রিং এর শুরু এবং শেষ থেকে পয়েন্টার শুরু করি তবে সেগুলি কিছু সময়ে ওভারল্যাপ হয়ে যাবে তাই এটি করার পরিবর্তে আমরা স্ট্রিংটিকে মাঝখান থেকে ভেঙ্গে বাম এবং ডান স্ট্রিং মেলাতে শুরু করব। যদি তারা মিলিত স্ট্রিংগুলির একটির সমান রিটার্ন সাইজ হয় তবে উভয় দিকে ছোট দৈর্ঘ্যের জন্য চেষ্টা করুন৷
অ্যালগরিদম
int longest(char str[], int n) START STEP 1 : DECLARE length AS 0 AND i AS n/2 STEP 2 : IF n < 2 THEN RETURN 1 STEP 3 :LOOP WHILE TILL str[i]!='\0' IF str[i] == str[length] THEN, INCREMENT length BY 1 INCREMENT i BY 1 ELSE IF length == 0 THEN, INCREMENT i BY 1 ELSE DECREMENT length BY 1 END IF END IF END WHILE RETURN length STOP
উদাহরণ
#include <stdio.h>
int longest(char str[], int n){
int length = 0, i = n/2;
if( n < 2 )
return 1;
while( str[i]!='\0' ){
//When we find the character like prefix in suffix,
//we will move the length and i to count the length of the similar prefix and suffix
if (str[i] == str[length]){
++length;
++i;
} else //When prefix and suffix not equal{
if(length == 0)
++i;
else
--length;
}
}
return length;
}
int main(int argc, char const *argv[]){
char str[] = {"abccmmabcc"};
int n = sizeof(str)/sizeof(str[0]);
int length = longest(str, n);
printf("Length = %d", length);
return 0;
} আউটপুট
যদি আমরা উপরের প্রোগ্রামটি চালাই তবে এটি নিম্নলিখিত আউটপুট তৈরি করবে:
Length = 4
