In tiền tố dài nhất của chuỗi đã cho, tiền tố này cũng là hậu tố của cùng một chuỗi trong C Program.

Cho một chuỗi trong đó chúng ta phải kiểm tra xem độ dài của tiền tố dài nhất cũng là hậu tố của chuỗi giống như có một chuỗi "abcab" vì vậy ở đây "ab" có độ dài 2 và là chuỗi con dài nhất có cùng tiền tố và hậu tố.

Ví dụ

Input: str[] = { “aabbccdaabbcc” }
Output: 6
Input: abdab
Output: 2

Nếu chúng ta bắt đầu con trỏ từ đầu và cuối chuỗi thì chúng sẽ bị chồng lên nhau tại một thời điểm nào đó, vì vậy thay vì làm như vậy chúng ta sẽ ngắt chuỗi từ giữa và bắt đầu khớp chuỗi trái và phải. Nếu chúng có kích thước trả về bằng nhau của bất kỳ một trong số các chuỗi đã so khớp, hãy thử độ dài ngắn hơn ở cả hai bên.

Thuật toán

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

Ví dụ

#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;
}

Đầu ra

Nếu chúng ta chạy chương trình trên thì nó sẽ tạo ra kết quả sau:

Length = 4