एक स्ट्रिंग को देखते हुए जिसमें हमें यह जांचना है कि सबसे लंबे उपसर्ग की लंबाई जो कि स्ट्रिंग का एक प्रत्यय भी है जैसे कि एक स्ट्रिंग "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